trueID

Tom đang lên kế hoạch trao thưởng cho gian hàng trò chơi của mình tại hội trại. Tom dự định cho người chiến thắng chọn một số tấm thẻ liên tiếp nhau trong số các tấm thẻ được đặt trên bàn. Trên mỗi tấm thẻ có ghi một số tiền tương ứng. Số tiền người chơi nhận được bằng tổng của số tiền lớn nhất và số tiền nhỏ nhất ghi trên các tấm thẻ đã chọn. Ví dụ: nếu chọn các tấm thẻ có giá trị 2, 6, 3, 8 thì số tiền nhận được sẽ là 8 + 2 = 10. Tom sẽ cho bạn biết trước số tiền trên từng tấm thẻ và thứ tự của chúng khi đặt trên bàn. Hãy giúp Tom tính số tiền lớn nhất mà người chiến thắng có thể nhận được để cậu có thể chuẩn bị phần thưởng chu đáo nhất (quy ước chỉ có duy nhất một người chiến thắng).

Đầu vào:

• Dòng đầu tiên chứa số nguyên T ($1 < T < 10000$) cho biết số lượng bộ test.
• Mỗi bộ test gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên N ($2 \leq N \le 10^5$) — số lượng tấm thẻ.
  • Dòng thứ hai chứa N số nguyên $a_1, a_2, ..., a_N$ — số tiền ghi trên mỗi tấm thẻ theo đúng thứ tự đặt trên bàn ($0 \le a_i \le 10^6$).
• Tổng của $N$ trên tất cả các bộ test không vượt quá $10^6$.

Đầu ra: Với mỗi bộ test, in ra số tiền mà Tom cần chuẩn bị.

Ví dụ 1:

Đầu vào:

4
4
12 9 12 5
2
10 10
4
3 3 3 3
5
1 2 3 4 5

Đầu ra:

21
20
6
9