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.

binary search

bitmasks

combinatorics

data structures

divide and conquer

*2200

No tag edit access

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

×
D. High Cry

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputDisclaimer: there are lots of untranslateable puns in the Russian version of the statement, so there is one more reason for you to learn Russian :)

Rick and Morty like to go to the ridge High Cry for crying loudly — there is an extraordinary echo. Recently they discovered an interesting acoustic characteristic of this ridge: if Rick and Morty begin crying simultaneously from different mountains, their cry would be heard between these mountains up to the height equal the bitwise OR of mountains they've climbed and all the mountains between them.

Bitwise OR is a binary operation which is determined the following way. Consider representation of numbers *x* and *y* in binary numeric system (probably with leading zeroes) *x* = *x*_{k}... *x*_{1}*x*_{0} and *y* = *y*_{k}... *y*_{1}*y*_{0}. Then *z* = *x* | *y* is defined following way: *z* = *z*_{k}... *z*_{1}*z*_{0}, where *z*_{i} = 1, if *x*_{i} = 1 or *y*_{i} = 1, and *z*_{i} = 0 otherwise. In the other words, digit of bitwise OR of two numbers equals zero if and only if digits at corresponding positions is both numbers equals zero. For example bitwise OR of numbers 10 = 1010_{2} and 9 = 1001_{2} equals 11 = 1011_{2}. In programming languages C/C++/Java/Python this operation is defined as «|», and in Pascal as «or».

Help Rick and Morty calculate the number of ways they can select two mountains in such a way that if they start crying from these mountains their cry will be heard above these mountains and all mountains between them. More formally you should find number of pairs *l* and *r* (1 ≤ *l* < *r* ≤ *n*) such that bitwise OR of heights of all mountains between *l* and *r* (inclusive) is larger than the height of any mountain at this interval.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 200 000), the number of mountains in the ridge.

Second line contains *n* integers *a*_{i} (0 ≤ *a*_{i} ≤ 10^{9}), the heights of mountains in order they are located in the ridge.

Output

Print the only integer, the number of ways to choose two different mountains.

Examples

Input

5

3 2 1 6 5

Output

8

Input

4

3 3 3 3

Output

0

Note

In the first test case all the ways are pairs of mountains with the numbers (numbering from one):

In the second test case there are no such pairs because for any pair of mountains the height of cry from them is 3, and this height is equal to the height of any mountain.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 13:18:00 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|