Hunter In Jury#12829

Hunter In Jury

3 секунди
512 мегабайтів
Складна

ICPC суддя Антон отримав на день народження лук та стріли.

Після останнього ICPC змагання у залі змагань залишилось кульок. Кульки розташовані у лінію так що -th та кулька розташована у точці з координатами (i,0,h_i), де h_i є додатнім цілим числом.

Антон вирішив використати ці кульки щоб потренувати свої мисливські здібності.

Антон розташувався у точці (0,0,0), та може стріляти з довільної цілої висоти, тобто з точки (0,0,h_j). Коли він вистрілює, стріла починає рухатись з (0,0,h_j) горизонтально у напрямку зростання першої координати. Тобто вона спочатку проходить (1,0,h_j), потім (2,0,h_j), і так далі.

Коли стріла потрапляє у кульку, кулька лопається, та висота стріли зменшується на один. Тобто, якщо координати були (d,0,h_j), вони стануть (d,0,h_j-1). Стріла продовжує рухатись горизонтально на новій висоті. Якщо висота зменшується до нуля, стріла падає на підлогу.

Зверніть увагу, що друга координата завжди буде . Вона задається для кращого розуміння умови.

Знайдіть мінімальну кількість стріл необхідну для того, щоб лопнути усі кульки.

Вхідні дані

Перший рядок містить одне ціле число (1 \le N \le 10^6).

Другий рядок містить цілих чисел h_i (1 \le h_i \le 10^6) — висота -ої кульки.

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading