В процессе раскрытия очередного секрета городка Гравити Фолз близнецам Дипперу и Мэйбл пришлось отправиться в таинственный лес, в чаще которого они набрели на заброшенный дом. Дом был очень старым, и близнецы не обнаружили в нем ничего примечательного, за исключением потайной комнаты, располагавшейся в подвальной части дома. Комната оказалась заперта, а на двери висел домофон.
Диппер твердо решил во что бы то ни стало открыть комнату. В этот раз ему повезло — на одной из страниц дневника он нашел ключ к разгадке кода, который необходимо ввести на домофоне, чтобы открыть дверь. В дневнике была записана некоторая последовательность чисел 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. При большем количестве чисел найдется такая пара, для которой неравенство выполняться не будет.