题目描述

小 Z 有一个长度为 $n$ 的非负整数序列 $A =\{a_1,a_2,\cdots,a_n\}$。

现在，小 Z 需要统计二元组 $(i,j)$ 的数量，满足 $1 \le i \le j \le n$ 且 $a_i \oplus a_{i+1} \oplus ... \oplus a_j \le \max\{a_i,a_{i+1},...,a_{j}\}$，其中 $\oplus$ 表示按位异或运算。

输入格式

从 xor.in 文件读入数据。

输入数据第一行包含一个正整数 $n$，表示序列长度。

第二行包含 $n$ 个整数，$a_1,a_2,\cdots,a_n$。

输出格式

输出到 xor.out 文件。

输出一行一个整数表示合法的二元组 $(i,j)$ 的数量。

样例

4
1 2 4 3

5

样例 2

点击链接 ex_xor2.in 和 ex_xor2.out 下载大样例 2 的输入数据和输出数据。

说明/提示

样例 1 解释

满足条件的二元组有 $(1,1),(1,4),(2,2),(3,3),(4,4)$。

数据范围

• 对于前 $20\%$ 的数据，$n \le 2*10^3$。
• 对于另外 $20\%$ 的数据，$a_i\le 8$。
• 对于另外 $20\%$ 的数据，$a_1 \le a_2 \le ... \le a_n$。
• 对于另外 $20\%$ 的数据， $a_i$ 在 $[0,2^{30})$ 范围内均匀随机生成。
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i <2^{30}$。