← 返回题目列表

Codeforces · 1991/A

A. 最大化最后一个元素

中文机器翻译题面 查看原题

给定一个由 $$$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$$$。