Беси и ее подружки играют в уникальную версию игры в покер с колодой из N (1 <= N <= 100,000) различных рангов, для удобства пронумерованных от 1 до N (в обычной колоде N=13). В этой игре имеется только один тип руки, который корова может играть: можно выбрать карту, помеченную i и карту, помеченную j и играть все карты с каждым значением от i до j. Такой тип руки называется "straight".
У Беси на руках сейчас ai карт ранга i (0 <= ai <= 100000). Помогите ей определить минимальное количество рук, которое она должна сыграть, чтобы избавиться от всех своих карт.
PROBLEM NAME: poker
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит значение величины ai.
Формат выходных данных
* Строка 1: Минимальное количество "straights", чтобы Беси избавилась от всех своих карт.
Примечание
Беси может играть следующие straight: 1-5 1-2 4-5 2-2 (2 штуки) 5-5 Всего 6, чтобы избавится от всех карт.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
4
1
2
3
|
6
|