Đề bài

Vova thích sô cô la. Cậu ấy đã mua một thanh sô cô la lớn gồm N miếng sô cô la nhỏ. Mỗi miếng sô cô la có một độ ngon nhất định, cụ thể miếng thứ i có độ ngon là ~A[i]~ ~(1 ≤ i ≤ N)~.

Mỗi lần, Vova có thể ăn miếng đầu trái hoặc miếng đầu phải trên thanh sô cô la. Vova luôn để phần cho em gái miếng sô cô la cuối cùng của thanh sô cô la sau khi cậu ta đã ăn ~N-1~ miếng. Vova có tính tham ăn nên cậu ấy muốn ăn được nhiều miếng ngon nhất có thể.

Biết tình trạng độ ngon của N miếng sô cô la, hãy xác định độ ngon của miếng sô cô la cuối cùng mà em gái Vova có thể nhận được.

Đầu vào:

Dòng đầu tiên của đầu vào chứa một số nguyên ~T~ biểu thị số bộ dữ liệu cần kiểm tra. Trong đó, mỗi bộ dữ liệu gồm:

• Dòng đầu chứa một số nguyên ~N~ ~(N <= 1000)~ cho biết độ dài thanh sô cô la (số miếng trên thanh kẹo).
• Dòng thứ hai chứa N số nguyên được phân cách bằng dấu cách biểu thị độ ngon tương ứng của mỗi miếng sô cô la nhỏ theo thứ tự từ đầu trái sang đầu phải thanh sô cô la.

Đầu ra:

Ứng với mỗi bộ dữ liệu đầu vào,in ra một dòng chứa đáp án tương ứng.

Ví dụ:

CHOCOLATE.INP:

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

CHOCOLATE.OUT:

1
1
2