MEX

题目描述

给定一个由 $0$、$1$、$2$ 组成的长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$,以及一个由 M、E、X 组成的长度为 $N$ 的字符串 $S=S_1S_2\dots S_N$。

求所有满足 $1 \leq i \lt j \lt k \leq N$ 且 $S_iS_jS_k = \text{MEX}$ 的整数三元组 $(i,j,k)$ 的 $\text{mex}(A_i,A_j,A_k)$ 之和。

这里,$\text{mex}(A_i,A_j,A_k)$ 表示既不等于 $A_i$、$A_j$ 也不等于 $A_k$ 的最小非负整数。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$S$

输出格式

以整数形式输出答案。

样例

4
1 1 0 2
MEEX

3

满足 $S_iS_jS_k = \text{MEX}$ 的三元组 $(i,j,k)\ (1 \leq i \lt j \lt k \leq N)$ 有以下两个:$(i,j,k)=(1,2,4),(1,3,4)$。

由于 $\text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0$,$\text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3$,答案为 $0+3=3$。

3
0 0 0
XXX

0

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

13

数据范围

• $3 \le N \le 2\times 10^5$
• $N$ 是整数
• $A_i \in \lbrace 0,1,2\rbrace$
• $S$ 是由 M、E、X 组成的长度为 $N$ 的字符串