Colored Midpoints

問題文

長さ $N$ の整数列 $A$ と、長さ $N$ の 0, 1 のみからなる文字列 $S$ が与えられる。

以下の条件をすべて満たす整数の組 $(i,j)$ の個数を求めよ。

• $1\le i<j\le N$
• $A_i=A_j$
• $i+j$ は偶数である。
• $S_{\frac{i+j}{2}}$ は 1 である。

制約

• $1\le N\le 5\times 10^4$
• $1\le A_i\le N$
• $S$ は 0, 1 からなる長さ $N$ の文字列である。
• 入力はすべて整数または文字列である。

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル 1

入力

8
1 2 1 3 1 2 1 3
00110100

出力

6

条件を満たす組 $(i,j)$ は、$(1,5),(1,7),(2,6),(3,5),(4,8),(5,7)$ の $6$ 個である。