B. 【GENOIP#45】xor

题目描述

给定一个长度为 $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

5

数据范围与提示

• 对于前 $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}$ 。

大样例