A14735 | Interesting Sections

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:

1. The minimum and maximum numbers are found on the segment of the array starting at $l$ and ending at $r$ .
2. 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.

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 a single number — the total number of segments that passed the check.