F. Interesting Sections
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.
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.

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