Problem Description

This problem is translated from PA 2024 Practice Round Mrówki.

There are $n$ ants on the number line. Ant $i$ is located at the point $x = i$. Each ant is facing either to the right (the positive direction of the number line) or to the left (the opposite of the positive direction). The ants are so small that we can treat them as independent points.

After the signal is given, all ants start moving at the same unit speed in the direction they are facing. If two ants collide (they are at the same point), they bounce off, meaning both of them change their moving direction and continue moving. It can be proven that after some time, no more collisions will happen. Write a program to compute how many times each ant will collide with other ants.

Input Format

The first line contains an integer $n\ (1 \le n \le 3 \times 10^5)$, representing the number of ants.

The second line contains a string of length $n$, consisting only of L and P. The $i$-th character describes the direction of ant $i$: if it is L, it initially faces left; if it is P, it initially faces right.

Output Format

Output one line with $n$ integers. The $i$-th integer should be the number of collisions between ant $i$ and other ants.

6
LPPLPL

0 1 3 3 2 1

Hint

The first ant initially faces left, so it will not collide with any other ant. The last ant will collide with the fifth ant at $x = 5.5$, then start moving to the right, and it will never stop again. The third ant will collide with the fourth ant at $x = 3.5$, then start walking to the left. The second ant will collide at $x = 3$, then turn left, and keep going forever after that.

Translated by ChatGPT 5