Interesting Sections solution codeforces

Interesting Sections solution codeforces

William has an array of non-negative numbers a1,a2,,ana1,a2,…,an. He wants you to find out how many segments lrl≤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 ll and ending at rr.
  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 nn (1n1061≤n≤106), the size of array aa.

The second line contains nn integers a1,a2,,ana1,a2,…,an (0ai10180≤ai≤1018), the contents of array aa.

Output

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

Examples
input

Copy
5
1 2 3 4 5
output

Copy
9
input

Copy
10
0 5 7 3 9 10 1 6 13 7
output

Copy
18

Leave a Comment

Your email address will not be published. Required fields are marked *