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