전투 드로이드

드쿠 백작은 중요한 임무에 드로이드 부대를 보내려 한다. 한 줄로 선 $n$대의 드로이드가 왼쪽에서 오른쪽으로 1번부터 $n$번까지 번호가 매겨져 있다. 백작은 이 줄의 연속된 구간을 부대로 고른다. 즉 $1 \le l \le r \le n$을 만족하는 $l$, $r$에 대해 $l$번부터 $r$번까지의 드로이드를 고른다. 드로이드 $i$의 AIQ(인공지능 계수)는 $a_i$이다.

같은 부대의 드로이드는 더 진보한 드로이드로 합쳐질 수 있다. 부대에 AIQ가 같은 $x$인 드로이드가 두 대 있으면, 둘이 합쳐져 AIQ가 $x + 1$인 드로이드 한 대가 된다.

드쿠는 부대의 모든 드로이드가 여러 번의 합치기를 거쳐 한 대가 될 수 있는 구간을 고르고 싶어 한다. 그런 구간의 개수를 구하라.

첫 줄에 드로이드의 수 $n$이 주어진다 ($1 \le n \le 200\,000$). 둘째 줄에는 각 드로이드의 AIQ 값 $a_i$가 $n$개 주어진다 ($1 \le a_i \le 10^9$).

드쿠가 부대로 고를 수 있는 구간의 개수를 한 줄에 출력한다.

첫 번째 예시에서는 길이가 1인 구간 세 개 외에 $[1, 1]$과 $[1, 1, 2]$도 조건을 만족한다. 두 번째 예시에서는 길이가 1인 구간 일곱 개 외에 길이가 4인 구간 네 개와 $[3, 4, 3]$ 구간 두 개도 조건을 만족한다.