Предметы
- Математика
- Русский язык
- Алгебра
- Английский язык
- Литература
- Физика
- Химия
- История
- Геометрия
- Биология
- География
- Другие предметы
- Қазақ тiлi
- Информатика
- Українська мова
- Обществознание
- Окружающий мир
- Українська література
- Музыка
- Немецкий язык
- Экономика
- Право
- Беларуская мова
- ОБЖ
- Французский язык
- Психология
- Технология
- Физкультура и спорт
- МХК
- Астрономия
- Кыргыз тили
- Оʻzbek tili
- Черчение
- Уход за собой
Сдать решение задачи 7-Интересное подмножество
Полный балл: 100
Ограничение времени: 1 с
Ограничение памяти: 512M
Ограничение размера стека: 64M
Задача 7: Интересное подмножество
Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем.
Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества.
Входные данные
Первая строка входных данных содержит целое число N — количество элементов исходного множества (1 ≤ N ≤ 105).
В следующих N строках записаны целые числа ai по одному в строке — элементы исходного множества (1 ≤ ai ≤ 2×109), упорядоченные по возрастанию значений.
Выходные данные
Программа должна вывести одно целое число — размер наибольшего интересного подмножества.
Система оценки
Решения, правильно работающие при N = 5, будут оцениваться в 20 баллов.
Решения, правильно работающие при N ≤ 12, будут оцениваться в 60 баллов.
Примеры
Ввод
Вывод
Пояснение
5
1
2
3
4
5
2
В множестве пять чисел: 1, 2, 3, 4, 5. В качестве интересного подмножества можно взять, например, подмножество {3, 5}. Его мощность равна 2 и все элементы этого подмножества больше 2. Интересного подмножества большего размера в данном примере не существует.