Minimize Maximum After Subarray Rotation

You are given an array of integers. Your task is to determine the minimum possible maximum element that can be obtained after applying a right rotation by one position to any contiguous subarray of the given array exactly once. In other words, by selecting a contiguous segment of the array and performing a right rotation (i.e. moving the last element of that segment to the first position), you want to minimize the maximum element in the array after the operation.

Formally, let \(a_1, a_2, \dots, a_N\) be the array. For any contiguous subarray \(a_l, a_{l+1}, \dots, a_r\) (with \(1 \leq l < r \leq N\)), a right rotation transforms it into \(a_r, a_l, a_{l+1}, \dots, a_{r-1}\). The goal is to choose some contiguous subarray (or equivalently, its indices) such that if the rotation is applied, the maximum element of the entire array is minimized. It turns out that an optimal strategy is to perform the rotation on a subarray ending at the second last element of the array, resulting in an answer equal to \(\max(a_1, a_2, \dots, a_{N-1})\).

Note: You must process multiple test cases.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. For each test case:

• The first line contains an integer \(N\) (the size of the array).
• The second line contains \(N\) space-separated integers representing the elements of the array.

You should read from stdin.

outputFormat

For each test case, output a single integer - the minimum possible maximum element after performing a right rotation on an optimal contiguous subarray. Each answer should be printed on a new line to stdout.

## sample

3
4
3 1 4 5
5
2 2 2 2 2
3
10 1 8

4
2
10

</p>