28403번 - K번째 스페이드 찾기

문제

유진이는 딜러와 카드 게임을 한다.

딜러는 앞면에 스페이드($\spadesuit$) 또는 하트($\heartsuit$) 문양이 그려져 있는 $N$장의 카드 묶음을 가지고 있다. 카드는 처음에 뒷면이 보이도록 임의의 순서로 쌓여 있다. 딜러는 모든 카드의 앞면을 알지만, 유진이는 각 카드의 앞면을 모른다.

딜러는 게임을 시작하기 전에 1ドル$ 이상 $N$ 이하의 정수 $K$를 부른다. 유진이의 목표는 위에서 $K$번째 스페이드 카드를 찾는 것이다. 이제 다음과 같이 게임이 진행된다.

• 딜러는 카드를 한 장씩 순서대로, 테이블에 뒷면으로 내려놓는다.
• 유진이는 아무 때나 딜러에게 동전 1ドル$개를 지불하고 “스탑!”을 외칠 수 있다. (딜러가 마지막 카드를 내려놓은 직후에도 가능하다.)
• 유진이가 “스탑!”을 외친 순간, 딜러는 지금까지 내려놓은 스페이드 카드와 하트 카드의 수를 각각 세어 유진이에게 알려준 뒤 계속해서 카드를 내려놓는다.

딜러가 모든 카드를 내려놓고 나면 딜러는 다시 원래 순서대로 카드를 정리한다. 그다음에 유진이에게 정답을 맞힐 기회가 단 한 번 주어진다. 유진이는 둘 중 하나의 선언을 할 수 있다.

• 카드 묶음에 $K$장 미만의 스페이드 카드가 존재한다고 선언한다.
• 카드 한 장을 지목해서, 해당 카드가 위에서 $K$번째 스페이드 카드임을 선언한다.

유진이의 선언이 올바르다면 유진이의 승리, 그렇지 않으면 딜러의 승리다.

유진이는 게임을 지는 것을 싫어하기 때문에, 어떤 경우에도 유진이가 승리할 수 있는 필승 전략으로 게임을 진행하려고 한다. 예를 들어, 딜러가 카드를 내려놓을 때마다 “스탑!”을 외치는 전략은 유진이가 반드시 $K$번째 카드를 찾을 수 있으므로 필승 전략이다.

유진이는 필승 전략 중에서 가장 적은 동전을 지불하는 전략을 사용하기로 했다. 어떠한 카드 배열이 주어지더라도 다른 필승 전략보다 작거나 같은 양의 동전을 지불해야 하며, 이러한 전략이 존재함을 증명할 수 있다.

처음 카드 배열이 입력으로 주어진다. 1ドル$부터 $N$까지의 모든 $K$ 값에 대해, 유진이가 딜러에게 지불해야 하는 동전의 개수가 각각 몇 개인지 구하시오.

입력

첫 번째 줄에 카드의 수 $N$이 주어진다. (1ドル\le N\le 10^6$)

두 번째 줄에 카드 묶음을 나타내는 길이 $N$의 문자열이 주어진다. $i$번째 문자는 위에서 $i$번째 카드의 문양을 나타내며, S는 스페이드, H는 하트이다.

출력

한 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 $K=i$일 때 유진이가 딜러에게 지불해야 하는 동전의 개수이다.

제한

노트

첫 번째 예제에서, 딜러가 $K=2$를 부른 경우의 예시를 보자.

• 유진이는 딜러가 2ドル$번째 카드를 내려놓은 뒤 “스탑!”을 외친다. 딜러는 유진이에게 지금까지 하트 1ドル$장과 스페이드 1ドル$장을 내려놓았다고 알려 준다.
• 이후 유진이는 딜러가 3,4,ドル\cdots ,9$번째 카드를 내려놓을 때마다 “스탑!”을 외친다. 딜러는 마찬가지로 유진이에게 내려놓은 하트와 스페이드의 개수를 알려준다.
• 딜러가 카드를 정리하고 나면, 유진이는 위에서 9ドル$번째 카드가 스페이드 카드임을 맞힐 수 있다.

유진이는 위와 같은 과정으로 8ドル$개의 동전을 지불하고 $K$번째 스페이드 카드를 찾을 수 있다.