Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем. Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества.

Входные данные
Первая строка входных данных содержит целое число N — количество элементов исходного множества (1 ≤ N ≤ 105).

В следующих N строках записаны целые числа ai по одному в строке — элементы исходного множества (1 ≤ ai ≤ 2×109), упорядоченные по возрастанию значений.

Выходные данные
Программа должна вывести одно целое число — размер наибольшего интересного подмножества.

Система оценки
Решения, правильно работающие при N = 5, будут оцениваться в

Решения, правильно работающие при N ≤ 12, будут оцениваться в

Примеры
Ввод

Вывод

Пояснение

5
1
2
3
4
5

2

В множестве пять чисел: 1, 2, 3, 4, 5. В качестве интересного подмножества можно взять, например, подмножество {3, 5}. Его мощность равна 2 и все элементы этого подмножества больше 2. Интересного подмножества большего размера в данном примере не существует

milkovvich    1   28.10.2021 09:39    19