Саша любит программировать. Однажды, во время одного очень долгого контеста Саша решил, что он устал и было бы не плохо немного передохнуть. Так он и поступил. Но так как Саша не простой парень, то и отдыхает он необычно. Во время отдыха Саша очень любит дорешивать когда-то нерешённые задачи, ведь дорешка очень важна.
А дорешать Саша решил следующую задачу:
Дан массив $$$a$$$ из $$$n$$$ целых чисел, необходимо найти количество смешных пар $$$(l, r)$$$ $$$(l \leq r)$$$. Чтобы проверить, что пара $$$(l, r)$$$ — смешная, обозначим $$$mid = \frac{l + r - 1}{2}$$$, тогда, если $$$r - l + 1$$$ — четное число, и $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$$$, то пара смешная. Иначе говоря $$$\oplus$$$ элементов левой половины подмассива с $$$l$$$ по $$$r$$$ должен быть равен $$$\oplus$$$ элементов правой половины. Где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Саше необходимо продолжить решать контест, а эту задачу он предложил решить вам.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — размер массива.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) — сам массив.
Выведите одно число — количество смешных пар. Вы должны учитывать только те пары, в которых $$$r - l + 1$$$ чётно.
5
1 2 3 4 5
1
6
3 2 2 3 7 6
3
3
42 4 2
0
Дорешивай задачи, будь как Саша!
В первом примере единственная смешная пара — это $$$(2, 5)$$$, так как $$$2 \oplus 3 = 4 \oplus 5 = 1$$$.
Во втором примере смешные пары $$$(2, 3)$$$, $$$(1, 4)$$$, и $$$(3, 6)$$$.
В третьем примере нет смешных пар.
| Codeforces Round 539 (Div. 2) |
|---|
| Закончено |
