Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

meet-in-the-middle

two pointers

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Interesting Sections

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Examples

Input

5 1 2 3 4 5

Output

9

Input

10 0 5 7 3 9 10 1 6 13 7

Output

18

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/12/2024 20:32:22 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|