Алексей разрабатывает автономных дроидов, которые могут взаимодействовать между собой. Он уже построил n дроидов, пронумерованных от 1 до n слева направо. Алексей решил выбрать в качестве отряда подотрезок этой шеренги. То есть, всех дроидов с номерами от l до r для некоторых l и r (1 ≤ l ≤ r ≤ n). Каждый дроид характеризуется своим AIQ - коэффициентом искусственного интеллекта. AIQ дроида номер i равен a_i.

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

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

Формат входных данных

В первой строке дано одно целое число n - количество дроидов в шеренге (1 ≤ n ≤ 200 000).

Во второй строке даны n целых чисел a_i - коэффициенты искусственного интеллекта дроидов (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

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

Пример

Примечание

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

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