Юра уверен, что он может все. Но сможет ли он решить эту задачу?
У него есть массив \(a\), состоящий из \(n\) положительных целых чисел. Назовем подмассив \(a[l...r]\) хорошим, если одновременно соблюдены следующие условия:
- \(l+1 \leq r-1\), т. е. подмассив имеет длину не менее \(3\);
- \((a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Другими словами, подмассив хороший, если побитовое исключающее ИЛИ (XOR) элементов в его концах равен сумме остальных элементов.
Юрий хочет посчитать общее количество хороших подмассивов. Чему оно равно?
Массив \(c\) является подмассивом массива \(d\), если \(c\) может быть получен из \(d\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Выходные данные
Выведите единственное целое число — количество хороших подмассивов.
Примечание
В примере есть \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 1 2 3 1 2 3 15
|
6
|
|
2
|
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854
|
2
|