Interesting Sections

2000ms

262144K

Description:

$\text{[math]}$

William has an array of non-negative numbers $$$a_1, a_2, \dots, a_n$$$. He wants you to find out how many segments $$$l \le r$$$ pass the check. The check is performed in the following manner:

The minimum and maximum numbers are found on the segment of the array starting at $$$l$$$ and ending at $$$r$$$.
The check is considered to be passed if the binary representation of the minimum and maximum numbers have the same number of bits equal to 1.

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the size of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$), the contents of array $$$a$$$.

Output:

Output a single number — the total number of segments that passed the check.

Sample Input:

5
1 2 3 4 5

Sample Output:

Sample Input:

10
0 5 7 3 9 10 1 6 13 7

Sample Output:

Informação

Provedor Codeforces

Código CF1609F