Для последовательности целых чисел \([x_1, x_2, \dots, x_k]\) обозначим декомпозицию следующим образом:
Будем обрабатывать последовательность слева направо, поддерживая список ее подпоследовательностей. Когда мы обрабатываем элемент \(x_i\), мы приписываем его в конец первой подпоследовательности в списке, для которой побитовое И последнего ее элемента и \(x_i\) больше \(0\). Если такой подпоследовательности в списке нет, создадим новую подпоследовательность с единственным элементом \(x_i\) и запишем ее в конец списка подпоследовательностей.
Например, рассмотрим декомпозицию последовательности \([1, 3, 2, 0, 1, 3, 2, 1]\):
- обрабатываем элемент \(1\), список подпоследовательностей пуст. Ни к одной подпоследовательности нельзя приписать \(1\), поэтому мы создаем новую подпоследовательность \([1]\);
- обрабатываем элемент \(3\), список подпоследовательностей — \([[1]]\). Так как побитовое И \(3\) и \(1\) равно \(1\), элемент добавляется в первую подпоследовательность;
- обрабатываем элемент \(2\), список подпоследовательностей — \([[1, 3]]\). Так как побитовое И \(2\) и \(3\) равно \(2\), элемент добавляется в первую подпоследовательность;
- обрабатываем элемент \(0\), список подпоследовательностей — \([[1, 3, 2]]\). Ни к одной подпоследовательности нельзя приписать \(0\), поэтому мы создаем новую подпоследовательность \([0]\);
- обрабатываем элемент \(1\), список подпоследовательностей — \([[1, 3, 2], [0]]\). Ни к одной подпоследовательности нельзя приписать \(1\), поэтому мы создаем новую подпоследовательность \([1]\);
- обрабатываем элемент \(3\), список подпоследовательностей — \([[1, 3, 2], [0], [1]]\). Так как побитовое И \(3\) и \(2\) равно \(2\), элемент добавляется в первую подпоследовательность;
- обрабатываем элемент \(2\), список подпоследовательностей — \([[1, 3, 2, 3], [0], [1]]\). Так как побитовое И \(2\) и \(3\) равно \(2\), элемент добавляется в первую подпоследовательность;
- обрабатываем элемент \(1\), список подпоследовательностей — \([[1, 3, 2, 3, 2], [0], [1]]\). Элемент \(1\) нельзя приписать ни к одной из первых двух подпоследовательностей, но можно приписать к третьей.
В результате получается список подпоследовательностей \([[1, 3, 2, 3, 2], [0], [1, 1]]\).
Пусть \(f([x_1, x_2, \dots, x_k])\) — количество подпоследовательностей, на которое декомпозируется последовательность \([x_1, x_2, \dots, x_k]\).
А теперь — сама задача.
Вам дана последовательность \([a_1, a_2, \dots, a_n]\), в которой каждый элемент — это целое число от \(0\) до \(3\). Пусть \(a[i..j]\) — это последовательность \([a_i, a_{i+1}, \dots, a_j]\). Вы должны посчитать \(\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])\).