Докраска забора
(Время: 1 сек. Память: 64 Мб Сложность: 31%)
Поликарпыч приехал на свою дачу и первым делом заметил свой старый недокрашенный забор. Некоторые доски забора уже были окрашены и Поликарпыч решил докрасить его так, чтобы все окрашенные доски, как старые, так и новые, образовывали непрерывный отрезок досок в заборе.
Поликарпыч может купить в магазине кисть ширины W, что позволит ему за один вертикальный мазок красить сразу W подряд идущих досок, где W – любое натуральное число.
К сожалению, из-за особенности местной экологии, никакую доску нельзя красить повторно, в том числе и свежеокрашенную.
Поликарпыч хочет купить одну кисть и с её помощью докрасить забор. Определите минимальное количество мазков, за которое это можно сделать.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n – количество уже окрашенных досок (1 ≤ n ≤ 3×105).
Вторая строка содержит n целых чисел xi – номера досок (1 ≤ xi ≤ 1018). Гарантируется, что номера досок не повторяются.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество мазков для докраски забора.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 3 5 8 | 3 |
2 | 4 1 4 5 8 | 2 |
Пояснение к примерам
В первом примере W=1, красить нужно доски с номерами 4, 6 и 7.
Во втором примере при W=2 за первый мазок можно покрасить доски с номерами 2 и 3, а за второй – 6 и 7.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|