Задача Chart. Кроме олимпиад по информатике, в нашей стране с некоторых пор стали проводить олимпиады по ИКТ. Видимо, и вам приходилось принимать в них участие. Автор задачи не очень понимает, в чем там соревнуются, но предлагает знатокам офисных пакетов такую задачу. Синоптик в Excel создал гистограмму из N столбцов. Каждый столбик имеет высоту, равную температуре в конкретный день. Ширина столбиков равна единице их высоты. Если считать, что максимально возможная температура (высота столбика) M, то вся гистограмма представляет собой поле N × M ячеек, часть которых закрашена, начиная с нижней клетки каждого столбика. Гистограмму напечатали, а затем разрезали на полоски шириной в одну клетку. Первая полоска - это самая низкая строка ячеек. К ее концу приложили начало второй полоски (вторая строка ячеек) и так далее. Помогите найти количество закрашенных фрагментов полоски, ведь знатоки офисных пакетов этого сделать не смогли.
Технические условия. Программа Chart читает с устройства стандартного ввода целое число N (1 ≤ N ≤ 105). В следующей строке N целых чисел - a1, a2, ..., an (1 ≤ ai ≤ 109) – температуры в течение каждого из N дней. Программа выводит на устройство стандартного вывода единственное число - искомую величину.
Примеры
|
Ввод |
Вывод |
Ввод |
Вывод |
|
5 |
6 |
4 |
3 |
Комментарий к примеру 1. Синоптик построил такую гистограмму:
После всех операций - 6 закрашенных фрагментов.