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