两个玩家玩游戏。
最初,黑板上写有 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$。每回合,玩家选择一个数字并将其从棋盘上删除。这一直持续到棋盘上只剩下一个数字,即。 e. $$$n - 1$$$ 回合。第一个玩家首先采取行动,然后玩家轮流进行。
第一个玩家想要最小化棋盘上剩下的最后一个数字,而第二个玩家想要最大化它。
您想知道如果两个玩家都采取最佳行动,$$$n - 1$$$ 回合后棋盘上会留下什么数字。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 棋盘上的数字数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
输出
打印一个将留在黑板上的数字。
示例
输入 #1
3 2 1 3
输出 #1
2
输入 #2
3 2 2 2
输出 #2
2
注意
在第一个示例中,第一个玩家删除了 $$$3$$$,第二个玩家删除了 $$$1$$$。 $$$2$$$ 留在板上。
在第二个示例中,无论玩家的操作如何,$$$2$$$ 都会留在棋盘上。