题目描述

有两名玩家进行一场游戏。

初始时，黑板上写有 $n$ 个整数 $a_1, a_2, \ldots, a_n$。每一回合，一名玩家选择一个数字并将其从黑板上擦除。这个过程持续到黑板上只剩下一个数字为止，即共进行了 $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$）。

输出格式

输出一个整数，表示最终黑板上剩下的数字。

说明/提示

在第一个样例中，第一名玩家擦除 $3$，第二名玩家擦除 $1$，黑板上剩下 $2$。

在第二个样例中，无论两名玩家如何操作，最终都会剩下 $2$。

由 ChatGPT 4.1 翻译

样例

3
2 1 3

2

3
2 2 2

2