4963：小 Z 的旅行
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 题目描述
小 Z 来到了 A 国旅行，A 国有 $n+1$ 个城市，它们的编号为 $0,1,2,\cdots,n$。这 $n+1$ 个城市由 $n$ 条道路组成，第 $i$ 条道路连接编号为 $i-1$ 和 $i$ 的两个城市，同时为了防止堵车，这些道路都是**单向**的。
小 Z 是一名旅行家。他将会在第 $0$ 天坐飞机到 A 国。在此之前，他查找了相关资料，知道了第 $1$ 天每条道路的方向。同时他了解到，每过一天， A 国的道路方向都会**反转**。即如果有一条道路在第 $1$ 天是 $a\rightarrow b$，那么第 $2$ 天道路变为 $a \leftarrow b$。
小 Z 是个急性子。当他某天走到一个城市的时候，一定会在**下一天**离开这个城市，如果没有可行的道路，他就会坐飞机离开，并结束这次旅行。
他想知道，对于每座城市，若小 Z 在第 $0$ 天由此开始旅行，最多可以走过多少个不同的城市。**小 Z 可以多次旅游同一个城市，同时可以随时结束旅行。**
## 输入格式
从 `travel.in` 文件读入数据。
第一行，一个正整数 $n$。
第二行，长度为 $n$ 的字符串 $s$。代表每条道路在**第 $1$ 天**的方向。
如果 $s_i=L$（$L$ 是字符） ，那么代表**第 $1$ 天**连接城市 $i-1$ 和 $i$ 的道路为 $i-1 \leftarrow i$，否则为 $i-1 \rightarrow i$。
## 输出格式
输出到 `travel.out` 文件。
输出一行 $n+1$ 个数，第 $i$ 个数表示小 Z 在第 $0$ 天抵达城市 $i-1$ 时最多可以经过多少个城市。
## 样例
```input1
6
LRRRLL
```
```output1
1 3 2 3 1 3 2
```
```input2
16
RRLLRRRRRRLRLRRR
```
```output2
2 3 1 3 3 2 2 2 2 6 1 6 1 6 2 2 1
```
## 说明/提示
对于所有的数据，保证 $1 \le n \le 2 \times 10^6$，$s_i \in \{L,R\}$。
|测试点编号|特殊限制|测试点编号|特殊限制|
|:--:|:--:|:--:|:--:|
|$1$|$n =1$|$9 \sim 11$|$n \le 7000$|
|$2$|$n = 2$|$12 \sim 15$|$n \le 10^5$|
|$3 \sim 5$|$n \le 8$|$16 \sim 17$|所有 $s_i$ 均相同|
|$6 \sim 8$|$n \le 100$|$18 \sim 20$|$n \le 2 \times 10^6$|