Завтра Зия примет участие в соревновании последовательностей. Число x≥0 называется вершиной некоторой последовательности, если последовательность 1,2,3,...,x−1,x,x−1,...,3,2,1 является подпоследовательностью данной последовательности. Силой каждой последовательности считается ее наибольшая вершина. Завтра все студенты пойдут на соревнование и победителем станет обладатель сильнейшей последовательности. Зия имеет последовательность a1,a2,a3,...,an. Он хочет захватить систему оценки соревнования и удалить из нее последовательности с большей силой чем у него самого. Однако, Зия не знает силу собственной последовательности, но очень хочет победить. Помогите ему посчитать силу собственной последовательности.
В первой строке задано количество n (1≤n≤105) чисел в последовательности Зии. В следующей строке записаны n целых чисел ai (1≤ai≤105) — элементы последовательности.
Выведите одно число — силу данной последовательности.