Busy Beaver 和 Busy Revaeb 之间长达一个世纪的竞争至今仍在持续。这一次，他们决定在一场双人游戏中一决高下。

给定一个包含 $N$ 个正整数的序列 $a_1, \dots, a_N$。Busy Beaver 和 Busy Revaeb 按轮次进行游戏，规则如下：

• Busy Beaver 选择序列中两个相邻的数字，将它们擦除，并写下这两个数字中较大的一个。
• Busy Revaeb 执行相同的操作，但写下的是这两个数字中较小的一个。

Busy Beaver 先手。当序列中只剩下一个数字 $X$ 时，游戏结束。Busy Beaver 希望最大化 $X$；Busy Revaeb 希望最小化 $X$。若双方均采取最优策略，求最终 $X$ 的值。

输入格式

第一行包含一个整数 $N$ ($1 \leq N \leq 2 \cdot 10^5$)，表示数组中元素的个数。

第二行包含 $N$ 个空格分隔的整数 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$)。

输出格式

输出一个整数，表示双方均采取最优策略时，数组中最终剩下的唯一元素的值。

评分

• ($15$ 分) $N \leq 3$。
• ($25$ 分) $1 \le a_i \le 2$。
• ($60$ 分) 无额外限制。

样例

输入格式 1

3
2 1 4

输出格式 1

2

说明

最终值不可能是 $4$，因为如果 Busy Beaver 试图通过在第一轮不选择 $4$ 来保留它，Busy Revaeb 可以在下一轮取走 $4$，使得最终剩下的值为 $1$ 或 $2$。最终值也不可能是 $1$，因为 Busy Revaeb 本可以在第一轮取走 $1$，从而确保最终值大于 $1$。

Busy Beaver 可以确保最终值至少为 $2$，而 Busy Revaeb 可以确保最终值至多为 $2$。因此，在最优策略下，最终值为 $2$。

输入格式 2

4
1 1 1 2

输出格式 2

1

说明

最终值要么是 $1$，要么是 $2$。如果 Busy Revaeb 的策略是尽快取走 $2$，那么他可以保证在轮到他操作后（第 $2$ 轮），序列中只剩下 $1$ —— 无论 Busy Beaver 在第 $1$ 轮如何移动。因此，当双方都采取最优策略时，最终值为 $1$。

提示

Sample Explanation 1 最终值不可能是 $4$，因为如果 Busy Beaver 试图通过在第一轮不选择 $4$ 来保留它，Busy Revaeb 可以在下一轮取走 $4$，使得最终剩下的值为 $1$ 或 $2$。最终值也不可能是 $1$，因为 Busy Revaeb 本可以在第一轮取走 $1$，从而确保最终值大于 $1$。

Busy Beaver 可以确保最终值至少为 $2$，而 Busy Revaeb 可以确保最终值至多为 $2$。因此，在最优策略下，最终值为 $2$。

Sample Explanation 2 最终值要么是 $1$，要么是 $2$。如果 Busy Revaeb 的策略是尽快取走 $2$，那么他可以保证在轮到他操作后（第 $2$ 轮），序列中只剩下 $1$ —— 无论 Busy Beaver 在第 $1$ 轮如何移动。因此，当双方都采取最优策略时，最终值为 $1$。