题目描述

有 $N$ 头奶牛站成一排，从左到右依次编号为 $1∼N$。

每头奶牛要么是根西牛（用 G 表示），要么是荷斯坦牛（用 H 表示）。

每头奶牛都写下了一份奶牛名单，其中第 $i$ 头奶牛写下的名单中包含 $[i,E_i]（i≤E_i≤N）$范围内的所有奶牛。

现在，我们要在每个品种的奶牛当中选出一个领导者。

要求，每个领导者写下的奶牛名单应满足以下两个条件中的至少一个：

• 名单中包含其品种的所有奶牛。
• 名单中包含另一品种的领导者。

请问，一共有多少个满足条件的选择方案。

输入格式

第一行包含整数 $N$。

第二行包含一个长度为$N$ 的由 G 和 H 构成的字符串，其中第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 为根西牛，H 为荷斯坦牛）。

第三行包含 $N$ 个整数$E_1,E_2,...,E_N$。

输出格式

一个整数，表示满足条件的选择方案数量。

4
GHHG
2 4 3 4

1

3
GGH
2 3 3

2

提示

$2≤N≤10^5,$
$i≤E_i≤N$, 保证根西牛和荷斯坦牛的数量均不小于 1。 保证至少存在一个满足条件的选择方案。

样例1解释

唯一满足条件的方案是选择奶牛 1 和奶牛 2 作为领导者，奶牛 1 的名单中包含奶牛 2（另一品种的领导者），奶牛 2 的名单中包含所有同品种奶牛。

其它方案均不满足条件，例如，选择奶牛 2 和奶牛 4 作为领导者就不可行，因为奶牛 4 的名单中既不包含另一品种的领导者，也不包含所有同品种奶牛。

样例2解释

一共有 2 种满足条件的选择方案：

• 选择奶牛 1 和奶牛 3。
• 选择奶牛 2 和奶牛 3。