Задача 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 зафарбованих фрагментів.