[USACO23JAN] Leaders B

题目描述

农夫约翰有 $N$ 头牛 $(2 \le N \le 10^5)$。每头牛的品种要么是 Guernsey，要么是 Holstein。通常情况下，牛站成一排，按顺序编号为 $1 \cdots N$。

在一天的过程中，每头牛都会写下一个牛的列表。具体来说，第 $i$ 头牛的列表包含从她自己（第 $i$ 头牛）开始到包括第 $E_i(i \le E_i \le N)$ 头牛的范围。

FJ 最近发现，每种牛的品种都有一个独特的领导者。FJ 不知道领导者是谁，但他知道每个领导者的列表必须包括其品种的所有牛，或者其他品种的领导者（或两者）。

帮助 FJ 计算可能成为领导者的牛对数。保证至少有一对可能的领导者。

输入格式

第一行包含 $N$。

第二行包含一个长度为 $N$ 的字符串，其中第 $i$ 个字符表示第 $i$ 头牛的品种（G 表示 Guernsey，H 表示 Holstein）。保证至少有一个 Guernsey 和一个 Holstein。

第三行包含 $E_1 \cdots E_N$。

输出格式

输出可能的领导者对数。

输入输出样例 #1

输入 #1

4
GHHG
2 4 3 4

输出 #1

1

输入输出样例 #2

输入 #2

3
GGH
2 3 3

输出 #2

2

说明/提示

样例 1 的解释

唯一有效的领导者对是 $(1,2)$。第 1 头牛的列表包含其他品种的领导者（第 2 头牛）。第 2 头牛的列表包含她品种的所有牛（Holstein）。

没有其他对是有效的。例如，$(2,4)$ 是无效的，因为第 4 头牛的列表不包含其他品种的领导者，也不包含她品种的所有牛。

样例 2 的解释

有两个有效的领导者对，$(1,3)$ 和 $(2,3)$。

评分

• 输入 $3-5$：$N \le 100$
• 输入 $6-10$：$N \le 3000$
• 输入 $11-17$：没有额外的限制。