Саша любит программировать. Однажды, во время одного очень долгого контеста Саша решил, что он устал и было бы не плохо немного передохнуть. Так он и поступил. Но так как Саша не простой парень, то и отдыхает он необычно. Во время отдыха Саша очень любит дорешивать когда-то нерешённые задачи, ведь дорешка очень важна.
А дорешать Саша решил следующую задачу:
Дан массив \(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\) обозначает операцию побитового исключающего ИЛИ.
Саше необходимо продолжить решать контест, а эту задачу он предложил решить вам.
Выходные данные
Выведите одно число — количество смешных пар. Вы должны учитывать только те пары, в которых \(r - l + 1\) чётно.
Примечание
Дорешивай задачи, будь как Саша!
В первом примере единственная смешная пара — это \((2, 5)\), так как \(2 \oplus 3 = 4 \oplus 5 = 1\).
Во втором примере смешные пары \((2, 3)\), \((1, 4)\), и \((3, 6)\).
В третьем примере нет смешных пар.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
|
1
|
|
2
|
6
3 2 2 3 7 6
|
3
|
|
3
|
3
42 4 2
|
0
|