← 返回题目列表

Codeforces · 749/C

C. 投票

中文机器翻译题面 查看原题

另类蛋糕制造 (ACM) 有 n 名员工。他们现在正在就一些非常重要的问题进行投票,世界主要媒体正在试图预测投票结果。

每位员工都属于两个派系之一:民主党派或共和党派,这两个派系对投票结果持有相反的意见。投票程序比较复杂:

1. n 名员工每人发表一份声明。他们从员工 1 开始,到员工 n 结束,一一做出陈述。如果到了第 i 个员工发表声明的时刻,他不再有投票权,他就跳过轮到他(并且不再参与本次投票)。
2. 当员工发表声明时,他不能采取任何行动,也不能声明其他员工之一不再有投票权。可以拒绝投票已经发表声明或等待发表声明的人。如果有人被拒绝投票,他直到最后都不再参与投票。
3. 当所有员工都完成发言后,重复该过程:再次,从 1 开始到 n 结束仍有资格投票的每个员工都进行发言。
4. 重复该过程,直到只剩下一名有资格投票的员工,并由他决定整个投票的结果。当然,他会投票支持适合他的部分的决定。

您知道员工将投票的顺序以及他们的最佳行为(并且他们还知道顺序以及谁属于哪个部分)。预测投票结果。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 员工数量。

下一行包含 n 个字符。如果第 i 个雇员来自民主党派,则第 i 个字符为“D”;如果他来自共和党,则第 i 个字符为“R”。

输出

如果投票结果适合共和党人,则打印“D”;如果共和党获胜,则打印“R”。

示例

输入 #1

5
DDRRR

输出 #1

D

输入 #2

6
DDRRRR

输出 #2

R

注意

考虑第一个样本的投票场景之一:

1. 员工 1 拒绝员工 5 投票。
2. 员工 2 拒绝员工 3 投票。
3. 员工 3 无投票权并跳过轮到他(他被员工 2 拒绝)。
4. 员工 4 拒绝员工 2 投票。
5. 员工 5 无投票权并跳过轮到他(他被员工 1 拒绝)。
6. 员工 1 否认员工 4。
7. 现在只有员工 1 有投票权,因此投票以共和党人获胜而结束。