codeforces#P1609F. Interesting Sections

    ID: 32536 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>binary searchdata structuresdivide and conquermeet-in-the-middle*2800

Interesting Sections

Description

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.

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.

Samples

5
1 2 3 4 5
9
10
0 5 7 3 9 10 1 6 13 7
18