For a sequence of integers $[x_1, x_2, \dots, x_k]$, let's define its decomposition as follows:

Process the sequence from the first element to the last one, maintaining the list of its subsequences. When you process the element $x_i$, append it to the end of the first subsequence in the list such that the bitwise AND of its last element and $x_i$ is greater than $0$. If there is no such subsequence in the list, create a new subsequence with only one element $x_i$ and append it to the end of the list of subsequences.

For example, let's analyze the decomposition of the sequence $[1, 3, 2, 0, 1, 3, 2, 1]$:

processing element $1$, the list of subsequences is empty. There is no subsequence to append $1$ to, so we create a new subsequence $[1]$;

processing element $3$, the list of subsequences is $[[1]]$. Since the bitwise AND of $3$ and $1$ is $1$, the element is appended to the first subsequence;

processing element $2$, the list of subsequences is $[[1, 3]]$. Since the bitwise AND of $2$ and $3$ is $2$, the element is appended to the first subsequence;

processing element $0$, the list of subsequences is $[[1, 3, 2]]$. There is no subsequence to append $0$ to, so we create a new subsequence $[0]$;

processing element $1$, the list of subsequences is $[[1, 3, 2], [0]]$. There is no subsequence to append $1$ to, so we create a new subsequence $[1]$;

processing element $3$, the list of subsequences is $[[1, 3, 2], [0], [1]]$. Since the bitwise AND of $3$ and $2$ is $2$, the element is appended to the first subsequence;

processing element $2$, the list of subsequences is $[[1, 3, 2, 3], [0], [1]]$. Since the bitwise AND of $2$ and $3$ is $2$, the element is appended to the first subsequence;

processing element $1$, the list of subsequences is $[[1, 3, 2, 3, 2], [0], [1]]$. The element $1$ cannot be appended to any of the first two subsequences, but can be appended to the third one.

The resulting list of subsequences is $[[1, 3, 2, 3, 2], [0], [1, 1]]$.

Let $f([x_1, x_2, \dots, x_k])$ be the number of subsequences the sequence $[x_1, x_2, \dots, x_k]$ is decomposed into.

Now, for the problem itself.

You are given a sequence $[a_1, a_2, \dots, a_n]$, where each element is an integer from $0$ to $3$. Let $a[i..j]$ be the sequence $[a_i, a_{i+1}, \dots, a_j]$. You have to calculate $\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 3$).


-----Output-----

Print one integer, which should be equal to $\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$.


-----Examples-----

Input
8
1 3 2 0 1 3 2 1
Output
71
Input
5
0 0 0 0 0
Output
35


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Sorting

Amortized analysis

Complete search

Dynamic programming

Divide and conquer

Data structures


Solutions:
def nextstate(q, x):
	i = 0
	for i in range(len(q)):
		if q[i] & x > 0:
			return q[:i] + (x,) + q[i + 1:]
	return q + (x,)
qs = [()]
trans = []
ptr = 0
while ptr < len(qs):
	q = qs[ptr]
	tb = []
	for x in range(1, 4):
		qn = nextstate(q, x)
		if qn not in qs:
			qs.append(qn)
		tb.append(qs.index(qn))
	trans.append(tb)
	ptr += 1
n = int(input())
a = [int(x) for x in input().split(' ')]
cnt = [0] * len(qs)
cnt[0] = 1
ans = 0
for (i, ai) in enumerate(a):
	cnt2 = [0] * len(qs)
	cnt2[0] = 1
	if ai == 0:
		for j in range(len(qs)):
			cnt2[j] += cnt[j]
		ans += (i + 1) * (n - i)
	else:
		for j in range(len(qs)):
			qn = trans[j][ai - 1]
			cnt2[qn] += cnt[j]
	for j in range(len(qs)):
		ans += cnt2[j] * len(qs[j])
	cnt = cnt2
print(ans)