K. 异或最大值
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

给出一个长度为 n 的非负整数序列 a，请输出满足下列条件的整数对 (l, r) 个数：

  • 1 ≤ l ≤ r ≤ n

其中， 表示按位异或，max(l, r) 表示 a 序列 [l, r] 区间的最大值。

Input

第一行，一个正整数 n（1 ≤ n ≤ 105），表示序列长度。

第二行，n 个非负整数 a1, a2, ..., an（0 ≤ ai < 230）。

Output

输出一个整数，表示满足条件的整数对 (l, r) 个数。

Examples
Input
9
2 0 0 8 1 5 1 4 7
Output
7
Input
8
1 9 9 4 0 5 2 5
Output
11
Note

对于样例一，满足条件的整数对为：(1, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (7, 8)。