该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

RBtree W

题目背景

\(yyx\): 我要一道第一题，红题就行。

\(sty\): 不，黑题。

\(yyx\): 第一题你出黑？

\(sty\): 那就出红黑树吧！

题目描述

输入\(N\)个字符串。

请你求出字符串出现次数处于中位数\(a_{ \frac{n+1}{2} }\)的字符串。若有多个字符串出现次数相等，输出字典序最小的那个。

输入格式

共\(N + 1\)行，第一行一个数字\(N\)，其后一行一个字符串。

输出格式

一行一个字符串

输入输出样例 #1

输入 #1

6
hello
world
world
goodbye
goodbye
goodbye

输出 #1

world

输入输出样例 #2

输入 #2

2
LP
Leo

输出 #2

Leo

说明/提示

\(N < 10^5\)