一位老师决定给他的学生提供太妃糖。他要求n名学生排队。由于老师很偏心,所以他按照以下规则来分发太妃糖。
他看着前两个学生,给了比另一个分数高的学生更多的太妃糖。如果他们有相同的标记,他们就会得到相同数量的太妃糖。从第一个学生到最后一个学生,每对相邻的学生都遵循相同的过程。
每个学生至少收到一颗太妃糖。你必须找到老师给每个学生的太妃糖数量,使得太妃糖的总数最小。
输入
输入的第一行包含学生人数 n (2 ≤ n ≤ 1000)。第二行给出 (n - 1) 个由“L”、“R”和“=”组成的字符。对于每对相邻的学生,“L”表示左边的学生得分较高,“R”表示右边的学生得分较高,“=”表示两人得分相等。
输出
输出由 n 个整数组成,用空格分隔,表示每个学生在队列中从第一个到最后一个收到的太妃糖数量。
示例
输入 #1
5 LRLR
输出 #1
2 1 2 1 2
输入 #2
5 =RRR
输出 #2
1 1 2 3 4