4029 - 【AB-1】游戏

Alice 和 Bob 在玩游戏。

现有一个长度为 n 的序列, 第 i 个数为 a_i 。Alice 和 Bob 轮流对序列进行操作, Alice 先手。

对于每次操作, Alice 可以选择两个相邻的数, 删除其中较大的, Bob 可以选择两个相邻的数, 删除其中较小的。

双方轮流操作至只剩下一个数。Alice 希望剩下的数尽量大, Bob 希望剩下的数尽量小。

如果两人都足够聪明, 求最后剩下的数的值。

输入

第一行一个整数 n。 第二行 n 个整数, 第 i 个数为 a_i

输出

输出一个数, 即最后剩下的数。

样例

输入

3
3 2 1

输出

3

输入

4
2 5 3 7

输出

2

提示

对于 50\% 的数据, 1 ≤ n ≤ 8

对于另外 10\% 的数据, a_i = 0

对于另外 10\% 的数据, a_i = 0a_i = 1

对于 100\% 的数据, 1 ≤ n,a i ≤ 100

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题