题目描述

Farmer John has $N$ cows $(2 \le N \le 10^5)$. Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered $1 \cdots N$ in this order.

Over the course of the day, each cow writes down a list of cows. Specifically, cow $i$ 's list contains the range of cows starting with herself (cow $i$) up to and including cow $E_i(i \le E_i \le N)$.

FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed's leader (or both).

Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.

输入格式

The first line contains $N$.

The second line contains a string of length $N$ , with the ith character denoting the breed of the $i$-th cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein.

The third line contains $E_1 \cdots E_N$.

输出格式

Output the number of possible pairs of leaders.

题目大意

题面描述

FJ 有 $N$ 头奶牛，每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。

每一头奶牛都有一个名单。

对于每一头奶牛都会输入一个数字 $E_i$，表示第 $i$ 头奶牛的名单上记录了从第 $i$ 头奶牛到第 $E_i$ 头奶牛的所有奶牛。

每一种奶牛都只有一位“领导者”，对于某一头牛 $i$，如果它能成为“领导者”仅当它满足以下条件的至少一个：

• 其记录的名单上包含它的品种的所有奶牛。
• 其记录的名单上记录了另一品种奶牛的“领导者”。

请求出有多少对奶牛可能成为两种奶牛的领导者，保证存在至少一种。

数据范围

对于 $100\%$ 的数据：$1\leq N\leq 2\times 10^5,i\leq E_i\leq N$。

4
GHHG
2 4 3 4

1

3
GGH
2 3 3

2

提示

样例 1 说明

只有一对奶牛符合要求，就是 (1,2)，首先第二头奶牛的 $E_i=4$，表示它的名单记录了 $2 \sim 4$ 的所有奶牛，包含了所有 H 品种的奶牛，所以它是 H 品种的领导者。然后第一头奶牛的名单中记录了 H 品种奶牛的领导者，所以第一头奶牛也是领导者。

样例 2 说明

There are two valid leader pairs, $(1,3)$ and $(2,3)$.

Scoring

• Inputs $3-5$: $N \le 100$
• Inputs $6-10$: $N \le 3000$
• Inputs $11-17$: No additional constraints.