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