Guillaume

사진 출처: flickr.com

Guillaume에게는 기억 속 자신의 모습을 더 좋게 만들기 위해 특정 시점 이전의 사건을 잊을 수 있는 독특한 능력이 있다. Guillaume과 Arnar는 포켓볼을 꽤 자주 치며, 당신에게는 두 사람의 경기 결과 기록이 있다. Guillaume은 자신의 승률이 최대가 되도록 마지막 $k$개의 경기만 집계하고, 그 이전의 모든 경기는 무시한다. Arnar는 항상 두 사람의 마지막 경기 결과를 기억하므로 Guillaume은 전체 경기 기록을 무시할 수는 없다. 승률은 승리 횟수를 유효한 경기 수로 나눈 비율로 정의한다. $k$의 값이 여러 개 가능하다면, Guillaume이 기억하기에 더 쉽도록 $k$이 최소가 되게 선택해야 한다.

두 선수가 경기를 무효로 하고 다시 시작하기로 결정하면 포켓볼 경기는 무승부가 된다. 경기가 무승부로 끝나면 그 경기에는 승자가 없다.

Guillaume에 따르면 점수는 얼마인가?

채점

그룹 | 점수 | 제한

1 | 10 | $n = 1$

2 | 30 | $1 \leq n \leq 100$

3 | 20 | $1 \leq n \leq 3 \cdot 10^5$, 기호 A와 G의 총개수는 최대 $1\,000$이다

4 | 40 | $1 \leq n \leq 3 \cdot 10^5$

입력은 두 줄로 구성된다. 앞의 줄에는 기록된 경기 수를 나타내는 하나의 정수 $n$이 주어진다. 뒤의 줄에는 Arnar와 Guillaume이 치른 경기의 결과를 나타내는 문자들의 수열이 주어진다. $i$-번째 기호는 $i$-번째 경기의 결과를 나타내며, Arnar가 이겼다면 A, Guillaume이 이겼다면 G, 무승부라면 D이다.

g-a 형식으로 한 줄을 출력한다. 여기서 $g$은 Guillaume에 따르면 Guillaume이 이긴 경기 수를 나타내는 정수이고, $a$은 Arnar가 이긴 경기 수이다.