4029 - 【AB-1】游戏

Alice 和 Bob 在玩游戏。

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

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

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

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

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

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

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

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

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

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