Стовпчикова діаграма#11802
Клітинки таблиці M \times N розфарбовані у синій та білий кольори. В -ому з стовпчиків синім зафарбовані a_i нижніх клітинок, причому a_i \ge 1. Таблицю розрізали на горизонтальні смужки шириною в одну клітинку. Перша смужка — це найнижчий рядок клітинок. До її кінця приклали початок другої смужки (другий рядок клітинок) і так далі. В результаті утворилася одна смужка довжини N \cdot M. Сегментом називаємо послідовність клітинок одного кольору, справа від якої міститься клітинка іншого кольору або кінець смужки, а зліва — клітинка іншого кольору або початок смужки. Скільки синіх сегментів в отриманій смужці?
У першому рядку два цілих числа та — кількість рядочків та стовпчиків таблиці відповідно (1 \le N \le 10^5, 1 \le M \le 10^9). В наступному рядку цілих чисел a_1, a_2, ..., a_n (1 \le a_i \le M) — кількість зафарбованих клітинок у кожному з стовпчиків.
Виведіть єдине число — кількість сегментів.
Приклад
Діаграма спершу виглядала ось так:
Після розрізання і склеювання ми б отримали таку смужку:
