水平线上有 $$$n$$$ 个人,每个人要么向左看,要么向右看。每个人都数着自己看向的方向有多少人。该行的值是每个人的计数之和。
例如,在 LRRLL 排列中,L 代表向左看的人,R 代表向右看的人,每个人的计数为 $$$[0, 3, 2, 3, 4]$$$,值为 $$$0+3+2+3+4=12$$$。
您将获得排队人员的初步排列。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,如果您可以改变最多 $$$k$$$ 人的方向,请确定该线的最大值。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 行的长度。
下面一行包含一个由 $$$n$$$ 个字符组成的字符串,每个字符都是 L 或 R,分别代表一个面向左或面向右的人——该行的描述。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。
输出
对于每个测试用例,输出 $$$n$$$ 以空格分隔的非负整数 - 如果您可以将每个 $$$k$$$ 的最多 $$$k$$$ 人的方向从 $$$1$$$ 更改为 $$$n$$$(含),则该线的最大值。
示例
输入 #1
6 3 LLR 5 LRRLL 1 L 12 LRRRLLLRLLRL 10 LLLLLRRRRR 9 LRLRLRLRL
输出 #1
3 5 5 16 16 16 16 16 0 86 95 98 101 102 102 102 102 102 102 102 102 29 38 45 52 57 62 65 68 69 70 44 50 54 56 56 56 56 56 56
注意
在第一个测试用例中:
- $$$k=1$$$:改变$$$1$$$人的方向,使线路RLR。总价值为$$$2+1+0=3$$$。
- $$$k=2$$$:改变$$$2$$$人的方向,使线路RLL。总价值为$$$2+1+2=5$$$。
- $$$k=3$$$:改变$$$2$$$人的方向,使线路RLL。总价值为$$$2+1+2=5$$$。请注意,您最多必须改变 $$$k$$$ 人的方向。
在第二个测试用例中,最佳方案是仅将所有 $$$k$$$ 的第一个人的方向从 $$$1$$$ 更改为 $$$5$$$(即,使线 RRRLL)。