Statement is not available in English language
F. Уютненько
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В уютном Нижнем Новгороде был брадобрей Глеб, который любил гулять по старым улочкам и изучать архитектурные шедевры. Всего в городе $$$n$$$ улиц, на улице $$$i$$$ ($$$1 \leq i \leq n$$$) находится $$$a_i$$$ зданий.

Однажды, гуляя по городу по какой-то подпоследовательности улиц $$$ i_1 \lt i_2 \lt \dots \lt i_k $$$, Глеб заметил, что для номеров улиц и зданий на них выполнено следующее:

  • $$$i_p- i_{p-1} \geq \min(a_{i_p}, a_{i_{p-1}})$$$ для всех $$$p = {2, \dots, k}$$$. Другими словами, разность соседних индексов подпоследовательности оказалась не меньше минимума числа зданий на соответствующих улицах.

Вам нужно найти максимальный размер подпоследовательности, по которой мог гулять Глеб.

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

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^6$$$)  — количество улиц.

Во второй строке записаны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — количество зданий на улицах с номерами $$$1, 2, \dots, n$$$.

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

В единственной строке выведите максимальное возможное значение $$$k$$$  — длину максимальной подпоследовательности, по которой мог гулять брадобрей Глеб.

Система оценки
ГруппаБаллыДоп. ограниченияКомментарий
$$$0$$$$$$0$$$—Тесты из условия
$$$1$$$$$$20$$$$$$n \le 10 $$$Каждый тест
$$$2$$$$$$20$$$$$$n \le 5000$$$Каждый тест
$$$3$$$$$$20$$$$$$ a_i \ не \ убывают $$$Каждый тест
$$$4$$$$$$10$$$$$$a_i \ не \ возрастают $$$Каждый тест
$$$5$$$$$$30$$$—Каждый тест
Примеры
Входные данные
1
1
Выходные данные
1
Входные данные
10
1 10 3 6 7 6 1 4 1 5
Выходные данные
7
Примечание

В первом примере брадобрей может пройтись только по первой улице.

Во втором примере брадобрей может пройтись по улицам с номерами $$${1, 3, 6, 7, 8, 9, 10}$$$. Действительно, $$$min(a_1, a_3) \le 2, min(a_3, a_6) \le 3, min(a_6, a_7) \le 1, \dots, min(a_9, a_{10}) \le 1 $$$.