Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Докраска забора

(Время: 1 сек. Память: 64 Мб Сложность: 31%)

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

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

К сожалению, из-за особенности местной экологии, никакую доску нельзя красить повторно, в том числе и свежеокрашенную.

Поликарпыч хочет купить одну кисть и с её помощью докрасить забор. Определите минимальное количество мазков, за которое это можно сделать.

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество уже окрашенных досок (1 ≤ n ≤ 3×105).

Вторая строка содержит n целых чисел xi – номера досок (1 ≤ xi ≤ 1018). Гарантируется, что номера досок не повторяются.

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

В выходной файл OUTPUT.TXT выведите минимальное количество мазков для докраски забора.

Примеры

INPUT.TXTOUTPUT.TXT
13
3 5 8
3
24
1 4 5 8
2

Пояснение к примерам

В первом примере W=1, красить нужно доски с номерами 4, 6 и 7.

Во втором примере при W=2 за первый мазок можно покрасить доски с номерами 2 и 3, а за второй – 6 и 7.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Вы все уже победители
 B. Заработай себе металлолома
 C. Обледенение
 D. Дата сайнс
 E. Вирусные воспоминания
 F. Докраска забора
 G. Скатерть
 H. История одного анекдота
 I. Кружок
 J. JuryGPT

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



Домен whatsoft.ru: купить в магазине доменных имен Рег.ру