Cho n viên socola xếp theo một hàng ngang. Minh chỉ có thể ăn viên đầu tiên hoặc cuối cùng của hàng. Lộc cũng là người thích ăn socola và anh ấy xin Minh viên cuối cùng còn lại sau khi Minh ăn hết. Tuy nhiên, vì là người tham lam, Minh chỉ ăn viên ngon hơn trong 2 viên đầu và cuối trong mỗi lần. Hãy tìm độ ngon của viên kẹo cuối cùng mà Lộc được ăn.

Input:

• Dòng 1: chứa số nguyên dương ~T~ là số test của bài.
• Dòng 2: chứa số ~N~.
• Dòng 3: lần lượt là độ ngon ~A_i~ của viên kẹo thứ ~i~.

Output:

• Dòng 1: In ra số nguyên dương ~k~ là độ ngon viên kẹo Lộc được ăn trên một dòng với mỗi test.

Example:

Input:

3
5
5 3 1 6 9
6
2 6 4 8 1 6
4
2 2 2 2

Output:

1
1
2

Constraints:

~1 \le T \le 100; 1 \le N \le 1000; 0 \le A[i] \le 1000~