페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5466

Leaders 1초 32MB

문제

Farmer John has N cows (2≤N≤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…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≤E_i≤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 ith 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…E_N.​ 


출력

Output the number of possible pairs of leaders. 


예제1

입력
4

GHHG

2 4 3 4
출력
1

예제2

입력
3

GGH

2 3 3
출력
2


출처

USACO 2023 January Bronze

역링크 공식 문제집만