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