e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Azərbaycan Respublika Olimpiadasının yarımfinalı 2018-2019

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

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

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

В первой строке записано одно целое число N – количество чисел в последовательности Зии. В следующей строке записаны N целых чисел, разделенных пробелом – элементы последовательности.

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

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

Ограничения

  • 1 ≤ N ≤ 105
  • 1 ≤ ai ≤ 105
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
2 10
Вихідні дані #1
0
Вхідні дані #2
3
1 2 3
Вихідні дані #2
1
Вхідні дані #3
5
1 10 2 3 1
Вихідні дані #3
2