Statement is not available in English language
E. Внезапные мишени
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андрей — отличный стрелок. Он никогда не промахивается. Ему очень нравится стрелять по внезапно появляющимся мишеням.

Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными числами.

Каждая мишень может «убита» в течение лишь одной секунды с момента её появления. Будем считать, что выстрел происходит мгновенно, поэтому поразить мишень можно в любой момент этой одной секунды: в самом её начале, в конце или в любой другой промежуточный момент между.

На перезарядку ружья у Андрея уходит ровно $$$1$$$ секунда, а одной перезарядки хватает только на один выстрел. В начальный момент времени (момент времени, равный $$$0$$$) ружьё у Андрея заряжено. Кроме того, Андрей успевает зарядить ружьё и выстрелить по мишени, если мишень появилась в тот же момент, в который он начал перезаряжать ружьё.

По известным моментам времени появления мишеней посчитайте максимальное количество мишеней, которые может поразить Андрей.

Входные данные

В первой строке вводится натуральное число $$$N$$$ — количество мишеней $$$(1 \le N \le 2 \cdot 10^5)$$$.

Во второй строке записано $$$N$$$ целых чисел — моменты появления мишеней $$$t_i$$$, выраженные в секундах от начала тренировки. Каждый момент появления мишени $$$t_i$$$ — это целое число из промежутка $$$[1; 10^9]$$$.

Выходные данные

Выведите одно целое число — максимальное количество мишеней, которые может поразить Андрей.

Система оценки

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

ПодгруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Тест из условия$$$0$$$—
$$$1$$$$$$N \le 10,\ t_i \le 10$$$$$$10$$$$$$0$$$
$$$2$$$$$$N \le 25,\ t_i \le 50$$$$$$15$$$$$$0,\ 1$$$
$$$3$$$$$$N \le 10^4,\ t_i \le 10^5$$$$$$20$$$$$$0,\ 1,\ 2$$$
$$$4$$$$$$N \le 10^5,\ t_i \le 10^8$$$$$$25$$$$$$0,\ 1,\ 2,\ 3$$$
$$$5$$$—$$$30$$$$$$0,\ 1,\ 2,\ 3,\ 4$$$
Пример
Входные данные
4
1 2 1 2
Выходные данные
3
Примечание

Так как поражение мишени происходит мгновенно, то можно поразить две мишени, появившиеся в один и тот же момент времени, если первую мишень поразить сразу, как только она появилась, а вторую после перезарядки ружья, в момент окончания одной секунды.

В примере Андрей может поразить максимум 3 мишени (например, первую, вторую и четвёртую), сделав выстрелы в моменты времени 1 (момент начала секунды), 2 (момент окончания первой секунды, сразу после перезарядки ружья) и 3 (момент окончания второй секунды, сразу после второй перезарядки ружья).