雪和 K 在一个长度为 n 的序列上博弈。
雪和 K 轮流行动。雪先手。每次操作方可以把序列从一个分割点分成非空的两个部分，然后由博弈的这一方删去其中一个部分，继续对剩下的一部分博弈。
具体的，第一轮由雪分割雪删去，第二轮由 K 分割 K 删去，第三轮由雪分割雪删去。
当最后只剩下一个数而一方无法操作时游戏终止。雪想让此时剩下的最后一个数尽量大，K 想让它尽量小。
假设两人绝对聪明，试求出最后剩下的数。
雪和 K 在一个长度为 n 的序列上博弈。
雪和 K 轮流行动。雪先手。每次操作方可以把序列从一个分割点分成非空的两个部分，然后由博弈的这一方删去其中一个部分，继续对剩下的一部分博弈。
具体的，第一轮由雪分割雪删去，第二轮由 K 分割 K 删去，第三轮由雪分割雪删去。
当最后只剩下一个数而一方无法操作时游戏终止。雪想让此时剩下的最后一个数尽量大，K 想让它尽量小。
假设两人绝对聪明，试求出最后剩下的数。
输入包含 T 组测试。每个输入数据第一行有一个整数 T。
每组测试第一行输入一个正整数 n。
每组测试第二行输入 n 个正整数，第 i 个正整数是 a_i。
对于每组测试输出一个整数，表示最后剩下的数。
2 5 1 4 3 1 5 4 1 3 3 1
5 1
样例第一组解释：如果雪选择把序列分成左边 4 个数右边 1 个数则可以直接删去左边，留下最大值。
| 测试点编号 | n\le |
|---|---|
| 1 | 5 |
| 2\sim 3 | 100 |
| 4\sim 6 | 1000 |
| 7\sim 10 | 10^5 |
对于所有数据，1\le T\le 10,1\le n\le 10^5,1\le a_i\le 10^9。
梦熊