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