尤里确信他可以做任何事情。但他能完成这个任务吗?
他有一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。如果同时满足以下条件,我们称子数组 $$$a[l...r]$$$ 为好:
- $$$l+1 \leq r-1$$$,i。 e.子数组的长度至少为 $$$3$$$;
- $$$(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$$$,其中 $$$\oplus$$$ 表示按位异或运算。
换句话说,如果两个边界元素的按位异或等于其余元素的总和,则子数组是好的。
Yurii 想要计算好子数组的总数。它等于什么?
数组 $$$c$$$ 是数组 $$$d$$$ 的子数组,如果 $$$c$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$d$$$ 获得。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2\cdot 10^5$$$) — $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \lt 2^{30}$$$) — $$$a$$$ 的元素。
输出
输出一个整数——好的子数组的数量。
示例
输入 #1
8 3 1 2 3 1 2 3 15
输出 #1
6
输入 #2
10 997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854
输出 #2
2
注意
示例中有 $$$6$$$ 好的子数组:
- $$$[3,1,2]$$$(两次)因为$$$(3 \oplus 2) = 1$$$;
- $$$[1,2,3]$$$(两次)因为$$$(1 \oplus 3) = 2$$$;
- $$$[2,3,1]$$$ 因为 $$$(2 \oplus 1) = 3$$$;
- $$$[3,1,2,3,1,2,3,15]$$$ 因为 $$$(3 \oplus 15) = (1+2+3+1+2+3)$$$。