给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$n$$$ 是奇数。
在一次操作中,您将从数组 $$$a$$$ 中删除两个相邻元素,然后连接数组的剩余部分。例如,给定数组 $$$[4,7,4,2,9]$$$,我们可以通过 $$$[\underline{4,7}, 4,2,9] \to [4,2,9]$$$ 和 $$$[4,7,\underline{4,2},9] \to 操作获得数组 $$$[4,2,9]$$$ 和 $$$[4,7,9]$$$分别为[4,7,9]$$$。但是,我们无法获取数组$$$[7,2,9]$$$,因为它需要删除不相邻的元素$$$[\underline{4},7,\underline{4},2,9]$$$。
您将重复执行此操作,直到 $$$a$$$ 中只剩下一个元素。
找出 $$$a$$$ 中剩余元素的最大可能值。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 99$$$;$$$n$$$ 为奇数)——数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 数组 $$$a$$$ 的元素。
请注意,所有测试用例的 $$$n$$$ 总和没有限制。
输出
对于每个测试用例,输出一个整数 - $$$a$$$ 中剩余元素的最大可能值。
示例
输入 #1
4 1 6 3 1 3 2 5 4 7 4 2 9 7 3 1 4 1 5 9 2
输出 #1
6 2 9 5
注意
在第一个测试用例中,数组 $$$a$$$ 是 $$$[6]$$$。由于只有一个元素,因此不需要进行任何操作。剩余元素的最大可能值为$$$6$$$。
在第二个测试用例中,数组 $$$a$$$ 是 $$$[1, 3, 2]$$$。我们可以删除前两个元素 $$$[\underline{1, 3}, 2] \to [2]$$$,或者删除最后两个元素 $$$[1, \underline{3, 2}] \to [1]$$$。因此,剩余元素的最大可能值为$$$2$$$。
在第三个测试用例中,数组 $$$a$$$ 是 $$$[4, 7, 4, 2, 9]$$$。最大化剩余元素的一种方法是 $$$[4, \underline{7, 4}, 2, 9] \to [\underline{4, 2}, 9] \to [9]$$$。因此,剩余元素的最大可能值为$$$9$$$。
在第四个测试用例中,数组 $$$a$$$ 是 $$$[3, 1, 4, 1, 5, 9, 2]$$$。可以证明剩余元素的最大可能值为$$$5$$$。