Вам дан массив \(a_1, a_2, \ldots, a_n\). Найдите количество троек чисел (\(x, y, z\)) таких, что:
- \(1 \leq x \leq y \leq z \leq n\), и
- \(f(x, y) \oplus f(y, z) > f(x, z)\).
Определим \(f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих троек.
Примечание
В первом наборе входных данных для массива \([6, 2, 4]\) есть 4 подходящие тройки чисел:
- (\(1\), \(2\), \(2\)): \((a_1 \oplus a_2) \oplus (a_2) = 4 \oplus 2 > (a_1 \oplus a_2) = 4\)
- (\(1\), \(1\), \(3\)): \((a_1) \oplus (a_1 \oplus a_2 \oplus a_3) = 6 \oplus 0 > (a_1 \oplus a_2 \oplus a_3) = 0\)
- (\(1\), \(2\), \(3\)): \((a_1 \oplus a_2) \oplus (a_2 \oplus a_3) = 4 \oplus 6 > (a_1 \oplus a_2 \oplus a_3) = 0\)
- (\(1\), \(3\), \(3\)): \((a_1 \oplus a_2 \oplus a_3) \oplus (a_3) = 0 \oplus 4 > (a_1 \oplus a_2 \oplus a_3) = 0\)
Во втором наборе входных данных подходящих троек нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
6 2 4
1
3
5
7 3 7 2 1
|
4
0
16
|