Для последовательности целых чисел $$$[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])$$$.