28785번 - Боевые дроиды 다국어

문제

Граф Дуку хочет отправить отряд дроидов на важное задание. Перед ним стоит шеренга из $n$ дроидов, пронумерованных от 1ドル$ до $n$ слева направо. Граф решил выбрать в качестве отряда подотрезок этой шеренги. То есть, всех дроидов с номерами от $l$ до $r$ для некоторых $l$ и $r$ (1ドル \le l \le r \le n$). Каждый дроид характеризуется своим AIQ --- коэффициентом искусственного интеллекта. AIQ дроида номер $i$ равен $a_i$.

Дроиды, находящиеся в одном отряде, могут объединяться в более продвинутых дроидов. Если в отряде есть два дроида с одинаковым AIQ, равным $x,ドル они могут объединиться в одного дроида с AIQ равным $x + 1$.

Дуку хочет выбрать такой отряд, чтобы все дроиды из отряда могли, в результате нескольких объединений, стать одним дроидом. Помогите ему посчитать количество различных отрезков шеренги, которые он может выбрать в качестве искомого отряда.

입력

В первой строке дано одно целое число $n$ --- количество дроидов в шеренге (1ドル \le n \le 200,000円$).

Во второй строке даны $n$ целых чисел $a_i$ --- коэффициенты искусственного интеллекта роботов (1ドル \le a_i \le 10^9$).

출력

В единственной строке выведите одно целое число --- количество отрезков шеренги, которые граф Дуку может выбрать в качестве желаемого отряда.

제한

노트

В первом примере помимо трёх подходящих отрезков длины 1ドル,ドル подходят отрезки $[1, 1]$ и $[1, 1, 2]$.

Во втором примере помимо семи подходящих отрезков длины 1ドル,ドル подходят все четыре отрезка длины 4ドル,ドル а также два отрезка $[3, 4, 3]$.