题目详情
返回题库题目描述
农夫约翰有 $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$。
数据范围：
- 输入 $3-5$：$N \le 100$
- 输入 $6-10$：$N \le 3000$
- 输入 $11-17$：没有额外的限制。
输出描述
输出可能的领导者对数。
提示
样例 1 的解释
唯一有效的领导者对是 $(1,2)$。第 1 头牛的列表包含其他品种的领导者（第 2 头牛）。第 2 头牛的列表包含她品种的所有牛（Holstein）。
没有其他对是有效的。例如，$(2,4)$ 是无效的，因为第 4 头牛的列表不包含其他品种的领导者，也不包含她品种的所有牛。
样例 2 的解释
有两个有效的领导者对，$(1,3)$ 和 $(2,3)$。