|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Андрей – отличный стрелок. Он никогда не промахивается. Ему нравится стрелять по внезапно появляющимся мишеням. Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные натуральными числами. Каждая мишень может быть поражена в течение лишь одной секунды с момента её появления. Будем считать, что выстрел происходит мгновенно, поэтому поразить мишень можно в любой момент на протяжении одной секунды, начиная с момента появления мишени. На перезарядку ружья у Андрея уходит ровно 1 секунда, а перезарядки хватает только на один выстрел. До начала тренировки ружьё у Андрея заряжено. По известным моментам появления мишеней требуется посчитать максимальное количество мишеней, которые может поразить Андрей. Формат входных данных В первой строке входного файла записано натуральное число N, не превосходящее 105, – это количество мишеней. Во второй строке записаны через пробел N натуральных чисел, не превосходящих 108, – это моменты появления мишеней, выраженные в секундах от начала тренировки. Эти числа могут повторяться, т.к. в один и тот же момент может появляться несколько мишеней. Формат выходных данных В выходном файле должно быть записано одно целое число – максимальное количество мишеней, которые может поразить Андрей. Пример
Комментарий к примеру: Так как поражение мишени происходит мгновенно, можно успеть поразить двумя выстрелами две одновременно появившиеся мишени, если одну из них поразить в момент её появления и сразу же перезарядить ружьё, а другую – ровно через секунду после её появления. Так, в приведённом примере Андрей может успеть поразить максимум 3 мишени (например, первую, вторую и четвёртую), сделав выстрелы в моменты времени 1, 2 и 3. Для отправки решений необходимо выполнить вход. |