개미

수직선 위에 개미 $n$마리가 서 있다. $i$번째 개미는 점 $i$에 있다. 각 개미는 오른쪽(좌표가 증가하는 방향) 또는 왼쪽(좌표가 감소하는 방향)을 보고 있다. 개미는 점으로 볼 수 있을 만큼 작다.

신호가 울리면 모든 개미가 보고 있는 방향으로 같은 속력 1로 걷기 시작한다. 두 개미가 같은 점에서 만나면 서로 튕겨 나온다. 두 개미 모두 방향을 바꾸고 계속 걷는다. 일정 시간이 지나면 더 이상 충돌이 일어나지 않는다는 것을 증명할 수 있다. 각 개미가 다른 개미와 몇 번 부딪히는지 계산하는 프로그램을 작성할 수 있겠는가?

첫 번째 줄에 개미의 수를 나타내는 정수 $n$ ($1 \le n \le 300\,000$)이 주어진다. 두 번째 줄에는 L과 P로만 이루어진 길이 $n$의 문자열이 주어진다. $i$번째 글자가 L이면 $i$번째 개미는 처음에 왼쪽을 본다. P이면 오른쪽을 본다.

$n$개의 정수를 공백 한 칸으로 구분하여 출력한다. $i$번째 정수는 $i$번째 개미가 튕긴 횟수이다.

예시에서 첫 번째 개미는 처음에 왼쪽을 보고 있어서 다른 개미와 한 번도 부딪히지 않는다. 마지막 개미는 점 5.5에서 다섯 번째 개미와 충돌한 뒤 오른쪽으로 걸어가며 멈추지 않는다. 세 번째 개미는 점 3.5에서 네 번째 개미와 부딪힌 뒤 왼쪽으로 걸어간다. 두 번째 개미는 점 3에서 세 번째 개미와 부딪혀 왼쪽으로 방향을 바꾸고 계속 걷는다.