Задача Chart. Кроме олимпиад по информатике, в нашей стране с некоторых пор стали проводить олимпиады по ИКТ. Видимо, и вам приходилось принимать в них участие. Автор задачи не очень понимает, в чем там соревнуются, но предлагает знатокам офисных пакетов такую ​​задачу. Синоптик в Excel создал гистограмму из N столбцов. Каждый столбик имеет высоту, равную температуре в конкретный день. Ширина столбиков равна единице их высоты. Если считать, что максимально возможная температура (высота столбика) M, то вся гистограмма представляет собой поле N × M ячеек, часть которых закрашена, начиная с нижней клетки каждого столбика. Гистограмму напечатали, а затем разрезали на полоски шириной в одну клетку. Первая полоска - это самая низкая строка ячеек. К ее концу приложили начало второй полоски (вторая строка ячеек) и так далее. Помогите найти количество закрашенных фрагментов полоски, ведь знатоки офисных пакетов этого сделать не смогли.

 Технические условия. Программа Chart читает с устройства стандартного ввода целое число N (1 ≤ N ≤ 105).  В следующей строке N целых чисел - a1, a2, ..., an (1 ≤ ai ≤ 109) – температуры в течение каждого из N дней. Программа выводит на устройство стандартного вывода единственное число - искомую величину.

ChartПримеры

Ввод

Вывод

Ввод

Вывод

5
5 1 4 2 3

6
 

4
1 3 3 1

3
 

 

Комментарий к примеру 1. Синоптик построил такую ​​гистограмму:

Chart

После всех операций - 6 закрашенных фрагментов.

© LIKT 1998-2018