题目描述

题目翻译

你有一个包含 $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, 7, 9]$，可以分别得到数组 $[4, 2, 9]$ 和 $[4, 7, 9]$。但是，无法通过删除非相邻元素来获得数组 $[7, 2, 9]$，如 $[\underline{4}, 7, \underline{4}, 2, 9]$。

你将重复进行此操作，直到数组 $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$ 中剩下的那个元素的最大可能值。

说明/提示

在第一个测试用例中，数组 $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$。

样例

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