E. Юра может все
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юра уверен, что он может все. Но сможет ли он решить эту задачу?

У него есть массив $$$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$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Входные данные

Первая строка содержит одно целое $$$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$$$.

Выходные данные

Выведите единственное целое число — количество хороших подмассивов.

Примеры
Входные данные
8
3 1 2 3 1 2 3 15
Выходные данные
6
Входные данные
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854
Выходные данные
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)$$$.