У Василия есть массив неотрицательных чисел \(a_1, a_2, \dots, a_n\). Он хочет, чтобы вы помогли ему узнать количество отрезков \(l \le r\), которые проходят проверку. Проверка отрезка выполняется следующим образом:
Первая строка содержит одно число \(n\) (\(1 \le n \le 10^6\)) — размер массива \(a\).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^{18}\)) — описание массива \(a\).
Выведите одно число — количество отрезков, прошедших проверку.
5 1 2 3 4 5
9
10 0 5 7 3 9 10 1 6 13 7
18
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач