← 返回题目列表

Codeforces · 984/A

A. 游戏

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

两个玩家玩游戏。

最初,黑板上写有 $$$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$$$ 都会留在棋盘上。