D. Lazy Jaber
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day Jaber found an array $$$a$$$ of size $$$n$$$. He wanted to count how many good subarrays are in this array.

Jaber considers a subarray $$$[a_l, a_{l+1}, .., a_r]$$$ good if he could choose a non-negative integer $$$x$$$ and after replacing each $$$a_i$$$ with $$$(a_i \oplus x)$$$ for each $$$i$$$ $$$(l \le i \le r)$$$ the resulting subarray $$$[a_l, a_{l+1}, .., a_r]$$$ becomes non-decreasing (where $$$\oplus$$$ is the bitwise XOR operation).

A subarray is the sequence of consecutive elements of the array.

A subarray $$$b$$$ of length $$$m$$$ is called non-decreasing if $$$b_i$$$ $$$\le$$$ $$$b_{i+1}$$$ for each $$$i$$$ such that $$$(1 \le i \lt m)$$$

As Jaber is too lazy and doesn't want to do any work today, he asks you to count this number for him.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — The size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — The array $$$a$$$.

Output

The number of good subarrays.

Examples
Input
3
2 1 2
Output
5
Input
5
5 2 1 4 7
Output
12
Input
8
4 2 2 3 6 2 1 4
Output
22