UOJ Logo Universal Online Judge

UOJ

#809. 【UNR #7】那些你不要的

附件下载 统计

小青鱼被神秘力量传送到了重(zhòng)庆市的一个陌生的街头。这里有一位智者,似乎知道很多东西,但你只有在一个古老的游戏中打败他,他才会认真和你对话。为了从智者那里知道些什么,小青鱼决定接受智者的游戏挑战。

这个游戏的规则是这样的:你面前有一个长度为 $n$ 的序列,序列由 $n$ 个整数构成,且保证 $n$ 是奇数。

两位玩家,小青鱼和空间的使者,将轮流进行操作。在每一轮中,玩家可以从序列中选择任意两个相邻的元素并将它们删除。删除后,这两个元素两侧的剩余序列将会自动合并。这样的操作将持续进行,直到序列中只剩下一个元素。

在这场游戏中,小青鱼是先手。他的目标是在游戏结束时让剩下的那个整数尽可能的大,而智者则希望让最后剩下的整数尽可能小。

面对如此高难度的挑战,小青鱼一下子就否定了几个过于简单的策略。然而究竟应该如何让最后剩下的整数尽可能大呢?小青鱼需要你的帮助。

请你帮助小青鱼找到最优的博弈策略,并输出当小青鱼以该策略进行博弈,且智者也以自己的最优策略进行对抗时,最后剩下的整数会是多少。

看着焦头烂额的你和小青鱼,智者提醒道:那些你不要的,那些被你忽视的,往往才是最重要的。

输入格式

第一行,一个整数 $T$,表示有 $T$ 组数据。

每组数据第一行一个奇数 $n$,表示序列长度。

第二行 $n$ 个整数 $a_1,\ldots,a_n$。

输出格式

对于每组数据,输出一行一个整数表示答案。

样例一

input

4
5
1 2 3 4 5
3
1 2 3
3
1 3 2
5
3 1 1 3 2

output

3
3
2
2

explanation

第一组数据,先手删掉 $1,2$,序列变为 $[3,4,5]$,然后后手删掉 $4,5$。

第二组数据,先手删掉 $1,2$。

第三组数据,先手删掉 $1,3$。

第四组数据,先手删掉 $1,1$,序列变为 $[3,3,2]$,然后后手删掉 $3,3$。

样例二/三

见附件下载。

数据范围

对于每个测试点:$T\geq 1$,$1\leq n\leq 10^6$,$1\leq a_i\leq n$。每个测试点内的所有数据的 $n$ 之和(记为 $\sum n$)不超过 $10^6$。

子任务编号 $n\leq$ $\sum n\leq$ 特殊性质 分值
1 $7$ $36000$ $30$
2 $2000$ $2000$ $a_i\leq 2$ $15$
3 $10^6$ $10^6$ $15$
4 $2000$ $2000$ $15$
5 $10^6$ $10^6$ $25$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$