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

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

2
2 10

0

3
1 2 3

1

5
1 10 2 3 1

2