A. 最大化最后元素

时间限制：1 秒
空间限制：256 MB

给定一个包含 $n$ 个整数的数组 $a$，其中 $n$ 是奇数。

在一次操作中，你将移除数组中两个相邻的元素，然后将剩余部分拼接起来。例如，给定数组 $[4,7,4,2,9]$，通过操作可以得到 $[4,2,9]$（删除 $[7,4]$）或 $[4,7,9]$（删除 $[4,2]$），但无法得到 $[7,2,9]$，因为那需要删除不相邻的两个元素。

你将重复执行该操作，直到数组中恰好剩下一个元素。

求这个最后剩下的元素的最大可能值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试数据的组数。

每组测试数据包含两行：

• 第一行包含一个整数 $n$（$1 \le n \le 99$，且 $n$ 为奇数）—— 数组长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 100$）—— 数组元素。

注意：所有测试数据的 $n$ 之和没有限制。

输出格式

对于每组测试数据，输出一个整数 —— 数组中能剩下的元素的最大可能值。

样例输入

4
1
6
3
1 3 2
5
4 7 4 2 9
7
3 1 4 1 5 9 2

样例输出

6
2
9
5

样例解释

• 第一个测试数据：数组为 $[6]$，无需操作，最后剩下的就是 $6$。
• 第二个测试数据：数组为 $[1,3,2]$。可以去掉前两个元素得到 $[2]$，或去掉后两个得到 $[1]$，最大可能值是 $2$。
• 第三个测试数据：数组为 $[4,7,4,2,9]$。一种最大化最后元素的操作为 $[4,\underline{7,4},2,9] \to [4,\underline{2,9}] \to [9]$，答案为 $9$。
• 第四个测试数据：数组为 $[3,1,4,1,5,9,2]$，可以证明最后剩下的元素最大值为 $5$