C. Про покраску забора
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бизон-Чемпион не только внимательный, но и очень трудолюбивый.

Бизон-Чемпион решил покрасить свой старый забор в свой любимый оранжевый цвет. Забор представляет из себя n вертикальных досок, расположенных в ряд. Между соседними досками нет зазора. Доски нумеруются слева направо начиная с единицы, i-я доска имеет ширину 1 метр и высоту ai метров.

Бизон-Чемпион купил в магазине кисть шириной 1 метр. Он умеет делать вертикальные и горизонтальные мазки этой кистью. Причем во время мазка кисть должна непрерывно и полностью касаться забора (смотрите пояснения примеров для лучшего понимания). Какое минимальное количество мазков придется сделать Бизону-Чемпиону, чтобы полностью покрасить забор? Обратите внимание, что разрешается красить один и тот же участок забора несколько раз.

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

В первой строке содержится целое число n (1 ≤ n ≤ 5000) — количество досок забора. Во второй строке записаны через пробел n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

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

Выведите целое число — минимальное количество мазков, необходимых для покраски всего забора.

Примеры
Входные данные
5
2 2 1 2 1
Выходные данные
3
Входные данные
2
2 2
Выходные данные
2
Входные данные
1
5
Выходные данные
1
Примечание

В первом примере можно покрасить забор за три мазка кистью: первый проходит на высоте 1 горизонтально по всем доскам, второй — на высоте 2 горизонтально красит первую и вторую доски, а третий мазок (он может быть как горизонтальный, так и вертикальный) докрашивает четвертую доску.

Во втором примере можно покрасить забор как двумя горизонтальными, так и двумя вертикальными мазками.

В третьем примере всего одна доска, которую можно покрасить, используя один вертикальный мазок.