CF 1991A - Maximize the Last Element

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

在一次操作中，您将从数组 a 中删除两个相邻元素，然后连接数组的剩余部分。例如，给定数组 [4,7,4,2,9]，我们可以通过操作 [4,7––––,4,2,9]→[4,2,9] 和 [4,7,4,2––––,9]→[4,7,9] 分别获得数组 [4,2,9]

和 [4,7,9]。但是，我们无法获得数组 [7,2,9]，因为它需要删除不相邻的元素 [4–,7,4–,2,9]。

您将重复执行此操作，直到 a 中只剩下一个元素。

找到 a 中剩余元素的最大可能值。

输入

每个测试包含多个测试用例。第一行包含一个整数 t（1≤t≤1000）— 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 n（1≤n≤99；n 为奇数）——数组 a 的长度。

每个测试用例的第二行包含 n 个整数 a1、a2、…、an（1≤ai≤100）——数组 a 的元素。

请注意，所有测试用例的 n 之和没有上限。

输出

对于每个测试用例，输出一个整数——a 中剩余元素的最大可能值。

-------------

整理数据不难发现，返回的都是奇数位元素的最大值，因为删除相邻的，每次保留的就还是奇数位的元素，留下来最大值肯定就是奇数位的最大值。