Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Column

 Задача ColumnЗадача 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

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"