eolymp
Соревнования

Техника двух указателей

Соревнования последовательностей

Завтра Зия примет участие в соревновании последовательностей. Число x0 называется вершиной некоторой последовательности, если последовательность 1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1 является подпоследовательностью данной последовательности. Силой каждой последовательности считается ее наибольшая вершина. Завтра все студенты пойдут на соревнование и победителем станет обладатель сильнейшей последовательности. Зия имеет последовательность a1, a2, a3, ..., an. Он хочет захватить систему оценки соревнования и удалить из нее последовательности с большей силой чем у него самого. Однако, Зия не знает силу собственной последовательности, но очень хочет победить. Помогите ему посчитать силу собственной последовательности.

Входные данные

В первой строке задано количество n (1n105) чисел в последовательности Зии. В следующей строке записаны n целых чисел ai (1ai105) - элементы последовательности.

Выходные данные

Выведите одно число - силу данной последовательности.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
2
2 10
Выходные данные #1
0
Входные данные #2
3
1 2 3
Выходные данные #2
1
Входные данные #3
5
1 10 2 3 1
Выходные данные #3
2
Источник Полуфинал Республиканской олимпиады Азербайджана 2018 - 2019