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]$.