Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем. Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества.
Входные данные
Первая строка входных данных содержит целое число 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. Интересного подмножества большего размера в данном примере не существует
1 часть решается 1 таблицей: решается таблицей. Вот сама таблица, вода и молоко не в бутылке, лимонад и вода не в банке, так как, сосуд с лимонадом находится между кувшином и сосудом с квасом, то получается, что лимонад и квас не в кувшине , так как стакан находится около банки и сосуда с молоком, то получается, что молоко находится не в банке и не в стакане. Получилось, раз молоко, не в банке не в стакане и не в бутылке, то он в кувшине. А значит остальные не могут быть в кувшине, раз там уже молоко. Теперь получается что вода не в кувшине, не в банкек и не в бутылке, получается она в стакане, а это значит что больше ничего в стакане быть не может, раз там уже вода. Теперь мы видим, что лимонад, не в банке, не в кувшине и не в стакане, значит он в бутылке. А это значит что оставшийся квас уже не в бутылке, так как он больше нигде не может быть он в банке.
Получается так в 1 действии: кувшин с молоком, бутылка с лимонадом, банка с квасом и стакан с водой.
Бутылка Стакан Кувшин Банка
Молоко - - + -
Лимонад + - - -
Квас - - - +
Вода - + - -
ответ: молоко в кувшине, лимонад в бутылке, квас в банке, вода в стакане.