Змагання послідовностей

Завтра Зія візьме участь в змаганні послідовностей. Число $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)$ — елементи послідовності.

Вихідні дані

Виведіть одне число — силу даної послідовності.

Приклади