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

对于整数序列 $[x_1, x_2, \dots, x_k]$，我们定义其分解如下：

从第一个元素开始依次处理该序列，同时维护一个子序列列表。当处理元素 $x_i$ 时，将其追加到当前子序列列表中第一个满足条件的子序列末尾：该子序列最后一个元素与 $x_i$ 的按位与（bitwise AND）结果大于 $0$。若列表中不存在满足该条件的子序列，则新建一个仅含单个元素 $x_i$ 的子序列，并将其追加到子序列列表末尾。

例如，我们分析序列 $[1, 3, 2, 0, 1, 3, 2, 1]$ 的分解过程：

• 处理元素 $1$：子序列列表为空，无法追加，因此新建子序列 $[1]$；
• 处理元素 $3$：子序列列表为 $[[1]]$；由于 $3 \mathbin{\&} 1 = 1 > 0$，将 $3$ 追加至第一个子序列；
• 处理元素 $2$：子序列列表为 $[[1, 3]]$；由于 $2 \mathbin{\&} 3 = 2 > 0$，将 $2$ 追加至第一个子序列；
• 处理元素 $0$：子序列列表为 $[[1, 3, 2]]$；由于对任意非零整数 $y$ 都有 $y \mathbin{\&} 0 = 0$，故无法追加，新建子序列 $[0]$；
• 处理元素 $1$：子序列列表为 $[[1, 3, 2], [0]]$；因 $1 \mathbin{\&} 2 = 0$、$1 \mathbin{\&} 0 = 0$，均不满足条件，故新建子序列 $[1]$；
• 处理元素 $3$：子序列列表为 $[[1, 3, 2], [0], [1]]$；因 $3 \mathbin{\&} 2 = 2 > 0$，将 $3$ 追加至第一个子序列；
• 处理元素 $2$：子序列列表为 $[[1, 3, 2, 3], [0], [1]]$；因 $2 \mathbin{\&} 3 = 2 > 0$，将 $2$ 追加至第一个子序列；
• 处理元素 $1$：子序列列表为 $[[1, 3, 2, 3, 2], [0], [1]]$；检查前两个子序列末尾元素 $2$ 和 $0$：$1 \mathbin{\&} 2 = 0$，$1 \mathbin{\&} 0 = 0$，均不满足；但 $1 \mathbin{\&} 1 = 1 > 0$，故可追加至第三个子序列。

最终得到的子序列列表为 $[[1, 3, 2, 3, 2], [0], [1, 1]]$。

令 $f([x_1, x_2, \dots, x_k])$ 表示序列 $[x_1, x_2, \dots, x_k]$ 经上述过程分解所得的子序列个数。

现在进入本题正文：

给定一个长度为 $n$ 的序列 $[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]).$$

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

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。

第二行包含 $n$ 个整数 $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])$.

输出一个整数，其值应等于 $\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$。