Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Егор работает на складе. Каждый день ему поступают `N` заказов на получение цепей из заданного количества звеньев `L_i`.
Обычно Егор отматывает от бесконечной катушки с цепью `L_i` звеньев, разгибает `L_i`-ое звено, чтобы
отцепить цепь от катушки, затем сгибает снова это звено, получая цепь нужной длины.
Марина предложила Егору разгибать `L_i+1`-ое звено, но при этом к концу дня у Егора будут оставаться
`N` одиночных разогнутых звеньев. Егор хотел бы, чтобы после выполнения всех заказов, у него не оставалось одиночных звеньев.
Из них можно собирать некоторые цепи, выбрав правильный порядок выполнения заказов.
Напишите программу, которая определяет минимальное количество звеньев, которые придется разогнуть и согнуть Егору.
В первой строке ввода содержится единственное целое число `N` (`1<=N<=10^5`) -- количество заказов.
Во второй строке ввода содержатся `N` целых чисел `L_i` (`1 <= L_i <= 10^5`) -- длина цепи в `i`-ом заказе.
Выведите единственное целое число -- минимальное количество звеньев, которые нужно разогнуть и согнуть.
```sample Пример ввода
5
5 2 4 6 1
```
```sample Пример вывода
3
```
Пояснение к примеру: Егор может отделить цепи длиной 5, 4, 6 по способу, предложенному Мариной, а из 3 одиночных звеньев сделать цепи длиной 2 и 1.
Это на 2 звена меньше, чем при способе, который он использовал ранее.
```sample Пример ввода 2
1
5
```
```sample Пример вывода 2
1
```
*Система оценки и описание подзадач*
||.u|Подзадача 1 (60 баллов)||
`1<=N<=100`
В этой подзадаче 6 тестов, каждый тест оценивается в 10 баллов.
||.u|Подзадача 2 (40 баллов)||
Ограничения из условий задачи.
Необходимые подзадачи: 1
В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов.
Во всех подзадачах баллы за каждый тест начисляются независимо. По запросу сообщается результат окончательной проверки на каждом тесте.
Начало
Рабочее место участника
Жадные алгоритмы