Завтра Зия примет участие в соревновании последовательностей. Число $x \ge 0$ называется вершиной некоторой последовательности, если последовательность $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ является подпоследовательностью данной последовательности. Силой каждой последовательности считается ее наибольшая вершина. Завтра все студенты пойдут на соревнование и победителем станет обладатель сильнейшей последовательности. Зия имеет последовательность $a_1, a_2, a_3, ..., a_n$. Он хочет захватить систему оценки соревнования и удалить из нее последовательности с большей силой чем у него самого. Однако, Зия не знает силу собственной последовательности, но очень хочет победить. Помогите ему посчитать силу собственной последовательности. \InputFile В первой строке задано количество $n~(1 \le n \le 10^5)$ чисел в последовательности Зии. В следующей строке записаны $n$ целых чисел $a_i~(1 \le a_i \le 10^5)$ --- элементы последовательности. \OutputFile Выведите одно число --- силу данной последовательности.