小克里斯知道玩多米诺骨牌没有什么乐趣,他认为这太随机了,不需要技巧。相反,他决定玩多米诺骨牌,进行一场“多米诺骨牌表演”。
Chris 将 n 块多米诺骨牌排成一行,将每块多米诺骨牌垂直放置。一开始,他同时将一些多米诺骨牌推向左侧或右侧。然而,在每两个朝同一方向推动的多米诺骨牌之间,至少有一个朝相反方向推动的多米诺骨牌。
每一秒之后,每张向左倒下的多米诺骨牌都会推动左侧相邻的多米诺骨牌。同样,向右倒下的多米诺骨牌会推动右侧相邻的多米诺骨牌。当多米诺骨牌从两侧倒在垂直的多米诺骨牌上时,由于力的平衡,它会保持静止。该图显示了该过程的一个可能的示例。
给定克里斯推动多米诺骨牌的初始方向,找出在该过程结束时留下垂直站立的多米诺骨牌的数量!
输入
第一行包含一个整数 n (1 ≤ n ≤ 3000),即该行中多米诺骨牌的数量。下一行包含长度为 n 的字符串 s。字符串 si 的第 i 个字符等于
- “L”,如果第 i 个多米诺骨牌已被推向左侧;
- “R”,如果第 i 个多米诺骨牌已被推到右侧;
- “.”,如果第 i 个多米诺骨牌尚未被推动。
保证如果 si = sj = "L" 且 i < j,则存在 i < k < j 且 sk = "R";如果 si = sj = "R" 且 i < j,则存在这样的 k:i < k < j 且 sk = "L"。
输出
输出一个整数,即过程结束时保持垂直的多米诺骨牌数量。
示例
输入 #1
14 .L.R...LR..L..
输出 #1
4
输入 #2
5 R....
输出 #2
0
输入 #3
1 .
输出 #3
1
注意
第一个示例案例如图所示。保持垂直站立的四块以橙色突出显示。
在第二个示例中,由于第一个棋子推倒了所有其他棋子,因此所有棋子都会掉落。
在最后一个示例中,单个部件没有被向任一方向推动。