题目描述
给定一个长度为 $n$ 的非负整数序列 $a_1,\cdots,a_n$。
统计二元组 $(i,j)$ 的数量，满足 $1\leq i\leq j\leq n$ 且 $a_i\oplus a_{i+1}\oplus \cdots\oplus a_j\leq \max\{a_i,a_{i+1}\cdots,a_j\}$，其中 $\oplus$ 是按位异或。
输入格式
输入数据第一行包含一个整数 $n$。
第二行包含 $n$ 个整数，表示序列 $a$。
输出格式
输出一行一个整数表示合法的二元组 $(i,j)$ 的数量。
样例
样例输入 1
4
1 2 4 3样例输出 1
5样例 2~3
见下发文件。
数据范围
- 对于前 $20\%$ 的数据，$n\leq 2\times 10^3$。
- 对于另外 $20\%$ 的数据，$a_i<8$。
- 对于另外 $20\%$ 的数据，$a_1\leq a_2\leq \cdots\leq a_n$。
- 对于另外 $20\%$ 的数据，$a_i$ 在 $[0,2^{30})$ 范围内均匀随机生成。
对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$0\leq a_i<2^{30}$。