Завтра Зія візьме участь в змаганні послідовностей. Число $x \ge 0$ називаєтся вершиною деякої послідовності, якщо послідовність $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ є підпослідовністю даної послідовності. Силою кожної послідовності вважається її найбільша вершина. Завтра всі студенти пійдуть на змагання і переможцем стане власник сильнішої послідовності. Зія має послідовність $a_1, a_2, a_3, ..., a_n$. Він хоче захватити систему оцінювання змагання і видалити з неї послідовності з більшою силою ніж у нього самого. Але, Зія не знає силу власної послідовності, і дуже хоче перемогти. Допоможіть йому порахувати силу власної послідовності. \InputFile В перному рядку задано кількість $n~(1 \le n \le 10^5)$ чисел в послідовності Зії. В наступному рядку записано $n$ цілих чисел $a_i~(1 \le a_i \le 10^5)$ --- елементи послідовності. \OutputFile Виведіть одне число --- силу даної послідовності.