CF1766E.Decomposition

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])$ .

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$ ).

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