Battle Droids

Time limit2sMemory limit1024 MB

Summary

Count contiguous segments where the sum of 2^a_i over the segment is a power of two, since equal AIQ values merge like binary addition.

Level: Medium7 of 10
Topics: Math, Hash map, Bit manipulation
Solved: No attempts yet

Problem

Count Dooku wants to send a squad of droids on an important mission. There are $n$ droids standing in a row, numbered from 1 to $n$ from left to right. Dooku picks a contiguous segment of the row as the squad, that is, all droids with numbers from $l$ to $r$ for some $1 \le l \le r \le n$ . The AIQ (artificial intelligence quotient) of droid $i$ is $a_i$ .

Droids in the same squad can merge into a more advanced droid. If the squad has two droids with the same AIQ $x$ , they can merge into one droid with AIQ $x + 1$ .

Dooku wants a squad where all droids can become a single droid after some number of merges. Count the number of different segments of the row that he can choose as the squad.

Input

The first line contains one integer $n$ , the number of droids ( $1 \le n \le 200\,000$ ). The second line contains $n$ integers $a_i$ , the AIQ values of the droids ( $1 \le a_i \le 10^9$ ).

Output

Print one integer, the number of segments Dooku can choose as the desired squad.

Note

In the first example, besides the three segments of length 1, the segments $[1, 1]$ and $[1, 1, 2]$ also fit. In the second example, besides the seven segments of length 1, all four segments of length 4 fit, and so do the two segments $[3, 4, 3]$ .

Examples2

Example 1
Input
```
3
1 1 2
```
Expected output
```
5
```
Example 2
Input
```
7
3 4 3 5 3 4 3
```
Expected output
```
13
```