Задача Column. На дні водойми знаходиться конструкція з двох вертикальних паралельних стінок (передня і задня) та дна одиничної ширини. Бокові та верхня стінки відсутні. Проміжок між стінками водолази заповнюють кубами зі стороною 1, складаючи з них стовпчики. Зрозуміло, що кожен кубик впритул дотикається до стінок і дна чи, можливо, інших кубиків. Стовпчики можуть мати різну висоту, але ніякий з них не буде вищим за стінки. Потім цю конструкцію виймають з води, при цьому дно весь час залишається горизонтальним. Скільки кубів можна було б помістити на те місце, яке після підйому буде зайняте водою? Густина кубів значно більша густини води.
Технічні умови. Програма Column зчитує з клавіатури ціле число N (N<=107) – кількість стовпчиків, а далі в тому ж рядку через пропуски N чисел Si ( 0 ≤ Si≤ 104) - кількість кубів у кожному стовпчику. Програма виводить на пристрій стандартного виведення єдине число – шукану величину.
Приклади.
|
Введення |
Виведення |
|
9 2 5 1 2 3 4 7 7 6 |
10 |
|
4 5 2 2 4 |
4 |