Условие:
Напиши код на питоне для решения данной задачи:
Андрей — отличный стрелок. Он никогда не промахивается. Ему очень нравится стрелять по внезапно появляющимся мишеням.
Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными числами.
Каждая мишень может «убита» в течение лишь одной секунды с момента её появления. Будем считать, что выстрел происходит мгновенно, поэтому поразить мишень можно в любой момент этой одной секунды: в самом её начале, в конце или в любой другой промежуточный момент между.
На перезарядку ружья у Андрея уходит ровно 1
секунда, а одной перезарядки хватает только на один выстрел. В начальный момент времени (момент времени, равный 0
) ружьё у Андрея заряжено. Кроме того, Андрей успевает зарядить ружьё и выстрелить по мишени, если мишень появилась в тот же момент, в который он начал перезаряжать ружьё.
По известным моментам времени появления мишеней посчитайте максимальное количество мишеней, которые может поразить Андрей.
Входные данные
В первой строке вводится натуральное число N
— количество мишеней (1≤N≤2⋅105)
.
Во второй строке записано N
целых чисел — моменты появления мишеней ti
, выраженные в секундах от начала тренировки. Каждый момент появления мишени ti
— это целое число из промежутка [1;109]
.
Выходные данные
Выведите одно целое число — максимальное количество мишеней, которые может поразить Андрей.