题目描述

题目译自 PA 2024 Runda próbna Mrówki

数轴上有 $n$ 只蚂蚁，第 $i$ 只位于点 $x=i$。每只蚂蚁面向右（数轴的正方向）或者向左（数轴正方向的反方向）。蚂蚁小到我们可以认为他们是独立的点。

信号发出后，所有蚂蚁开始以相同的单位速度朝它们面向的方向前进。如果两只蚂蚁相撞（位于同一点），它们就会弹开，也就是说，它们都会改变行进方向，继续前进。可以证明，经过一定时间后，不会再发生碰撞。你能编写一个程序，计算出每只蚂蚁会与其他蚂蚁碰撞多少次吗？

输入格式

第一行一个整数 $n\ (1\le n\le 300\,000)$，表示蚂蚁的数量。

第二行包含一个长为 $n$ 的字符串，字符串仅包含 L 和 P。其中第 $i$ 个字符表示蚂蚁 $i$ 面向的方向，如果为 L，则初始面向左，如果为 P，则初始面向右。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 只蚂蚁与其他蚂蚁的碰撞次数。

6
LPPLPL

0 1 3 3 2 1

提示

第一只蚂蚁一开始面向左，不会与其他蚂蚁碰撞。最后一只蚂蚁会在 $x=5.5$ 处与第五只蚂蚁相撞，然后开始向右行进，并且再也不会停下来。第三只蚂蚁在 $x=3.5$ 处与第四只蚂蚁碰撞后，开始向左行走。第二只蚂蚁会在 $x=3$ 处碰撞，然后向左转，之后一直走下去。