3860. [USACO23 Jan Bronze] Leaders

【题目描述】

有 $N$ 头奶牛站成一排，从左到右依次编号为 $1 \sim 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$。

【输出格式】

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

【样例1输入】

4
GHHG
2 4 3 4

【样例1输出】

1

【样例1说明】

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

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

【样例2输入】

3
GGH
2 3 3

【样例2输出】

2

【样例2说明】

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

选择奶牛 $1$ 和奶牛 $3$。

选择奶牛 $2$ 和奶牛 $3$。

【数据规模与约定】

测试点 $3-5:\ N≤100$

测试点 $6-10:\ N≤3000$

对于 $100\%$ 的数据，$2≤N≤10^5,i≤E_i≤N$，保证根西牛和荷斯坦牛的数量均不小于 $1$。

保证至少存在一个满足条件的选择方案。