E. Декомпозиция
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 3$$$).

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

Выведите одно целое число, равное $$$\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$$$.

Примеры
Входные данные
8
1 3 2 0 1 3 2 1
Выходные данные
71
Входные данные
5
0 0 0 0 0
Выходные данные
35