Maximize the Last Element
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

You are given an array $$$a$$$ of $$$n$$$ integers, where $$$n$$$ is odd.

In one operation, you will remove two adjacent elements from the array $$$a$$$, and then concatenate the remaining parts of the array. For example, given the array $$$[4,7,4,2,9]$$$, we can obtain the arrays $$$[4,2,9]$$$ and $$$[4,7,9]$$$ by the operations $$$[\underline{4,7}, 4,2,9] \to [4,2,9]$$$ and $$$[4,7,\underline{4,2},9] \to [4,7,9]$$$ respectively. However, we cannot obtain the array $$$[7,2,9]$$$ as it requires deleting non-adjacent elements $$$[\underline{4},7,\underline{4},2,9]$$$.

You will repeatedly perform this operation until exactly one element remains in $$$a$$$.

Find the maximum possible value of the remaining element in $$$a$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 99$$$; $$$n$$$ is odd) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — the elements of the array $$$a$$$.

Note that there is no bound on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output a single integer — the maximum possible value of the remaining element in $$$a$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the array $$$a$$$ is $$$[6]$$$. Since there is only one element, no operations are needed. The maximum possible value of the remaining element is $$$6$$$.

In the second test case, the array $$$a$$$ is $$$[1, 3, 2]$$$. We can remove the first two elements $$$[\underline{1, 3}, 2] \to [2]$$$, or remove the last two elements $$$[1, \underline{3, 2}] \to [1]$$$. Therefore, the maximum possible value of the remaining element is $$$2$$$.

In the third test case, the array $$$a$$$ is $$$[4, 7, 4, 2, 9]$$$. One way to maximize the remaining element is $$$[4, \underline{7, 4}, 2, 9] \to [\underline{4, 2}, 9] \to [9]$$$. Therefore, the maximum possible value of the remaining element is $$$9$$$.

In the fourth test case, the array $$$a$$$ is $$$[3, 1, 4, 1, 5, 9, 2]$$$. It can be shown that the maximum possible value of the remaining element is $$$5$$$.

Example input:
4
1
6
3
1 3 2
5
4 7 4 2 9
7
3 1 4 1 5 9 2

Example output:
6
2
9
5

Editorial:
Hint 1
Consider the parity of the position.
Solution
The answer is the maximum value of the elements at odd indices.
Proof
1. Any element at an odd index can be preserved until the end. Since each element at an odd index has an even number of elements on both sides, pairs of adjacent elements can be removed from left to right until only the element at the odd index remains. For example, if you want to keep the element at the $$$i$$$-th position, you can remove the elements at positions $$$1$$$ and $$$2$$$, $$$3$$$ and $$$4$$$, and so on, until the elements at positions $$$i-2$$$ and $$$i-1$$$ are removed. Then, continue removing elements at positions $$$i+1$$$ and $$$i+2$$$, and so on, until the elements at positions $$$n-1$$$ and $$$n$$$ are removed. Therefore, any element at an odd index can be preserved through this method.
2. No element at an even index can be preserved until the end. Since $$$n$$$ is odd, there are more elements at odd indices than at even indices. Each operation removes one element at an odd index and one element at an even index. Since there are always more elements at odd indices, the last remaining element must be at an odd index.