对于整数序列 $$$[x_1, x_2, \dots, x_k]$$$,我们将其分解定义如下:
处理从第一个元素到最后一个元素的序列,维护其子序列的列表。处理元素 $$$x_i$$$ 时,将其附加到列表中第一个子序列的末尾,使其最后一个元素与 $$$x_i$$$ 的按位 AND 大于 $$$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])$$$。
示例
输入 #1
8 1 3 2 0 1 3 2 1
输出 #1
71
输入 #2
5 0 0 0 0 0
输出 #2
35