Тайная комната
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
secretroom.in
вывод
secretroom.out

В процессе раскрытия очередного секрета городка Гравити Фолз близнецам Дипперу и Мэйбл пришлось отправиться в таинственный лес, в чаще которого они набрели на заброшенный дом. Дом был очень старым, и близнецы не обнаружили в нем ничего примечательного, за исключением потайной комнаты, располагавшейся в подвальной части дома. Комната оказалась заперта, а на двери висел домофон.

Диппер твердо решил во что бы то ни стало открыть комнату. В этот раз ему повезло — на одной из страниц дневника он нашел ключ к разгадке кода, который необходимо ввести на домофоне, чтобы открыть дверь. В дневнике была записана некоторая последовательность чисел a длины n и говорилось, что кодом является максимальная по количеству чисел её подпоследовательность, для каждой пары чисел которой выполняется следующее неравенство: ai - aj < j - i. Помогите Дипперу найти длину кода.

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

В первой строке входного файла дано число n — количество элементов последовательности a (1 ≤ n ≤ 106).

В следующей строке даны элементы последовательности — целые неотрицательные числа ai (1 ≤ ai ≤ 109).

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

Выведите единственное число — количество чисел в коде, с помощью которого Диппер сможет открыть дверь тайной комнаты.

Примеры

Входные данные
3
1 2 2
Выходные данные
3
Входные данные
6
5 3 5 6 6 5
Выходные данные
4

Примечание

В первом тестовом примере a0 = 1, a1 = 2, a2 = 2. Рассмотрев все пары чисел, можно убедиться, что для каждой из них неравенство выполняется:

1) a0 - a1 = 1 - 2 < 1 - 0.

2) a1 - a2 = 2 - 2 < 2 - 1.

3) a0 - a2 = 1 - 2 < 2 - 0.

Во втором примере неравенства будут выполняться, например, при выборе чисел с индексами 1, 2, 3 и 4. При большем количестве чисел найдется такая пара, для которой неравенство выполняться не будет.