Busy Beaver rất thích dành những buổi chiều tại Banana Lounge của MIT. Anh ấy quyết định giúp đỡ bằng cách xếp các thùng chuối! Anh ấy cần thu thập hàng tồn kho từ $N$ căn phòng liên tiếp, được sắp xếp thành một hàng duy nhất và đánh số từ $1$ đến $N$ từ trái sang phải. Do kiến trúc độc đáo của các tòa nhà tại MIT, mỗi phòng $i$ có một chiều cao trần cụ thể là $h_i$.

Busy Beaver cần chọn một phòng $k$ ($1 \le k \le N$) để làm Trung tâm chính (Main Hub). Sau đó, $N$ người bạn của anh ấy, mỗi người từ một phòng, sẽ mang một chồng thùng chuối thẳng đứng từ phòng xuất phát $i$ của họ trực tiếp đến phòng trung tâm $k$. Vì họ phải đi theo một đường thẳng, số lượng thùng tối đa họ có thể mang bị giới hạn bởi chiều cao trần tối thiểu trên đường đi của họ.

Về mặt hình thức, số lượng thùng chuối được vận chuyển bởi người bạn bắt đầu từ phòng $i$ đến phòng trung tâm $k$ là:

• $\min(h_i, h_{i+1}, \dots, h_k)$ nếu $i \le k$.
• $\min(h_k, h_{k+1}, \dots, h_i)$ nếu $i > k$.

Tổng số thùng chuối tập trung tại trung tâm là tổng số thùng được vận chuyển bởi tất cả $N$ người bạn, đó là:

$$\sum_{i=1}^{k-1} \min(h_i, \dots, h_k) + h_k + \sum_{i=k+1}^{N} \min(h_k, \dots, h_i)$$

May mắn thay, Busy Beaver có một người bạn làm việc tại bộ phận Cơ sở vật chất của MIT. Trước khi các người bạn bắt đầu vận chuyển thùng, anh ấy có thể yêu cầu cải tạo nhiều nhất một phòng (không được là phòng trung tâm $k$ đã chọn) để thay đổi chiều cao trần $h_i$ của nó thành bất kỳ giá trị nào.

Số lượng thùng chuối tối đa mà Busy Beaver có thể tập trung tại Trung tâm chính sau khi chọn vị trí trung tâm $k$ tối ưu và thực hiện cải tạo nhiều nhất một trần nhà là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^5$) — số lượng bộ dữ liệu kiểm tra. Dòng đầu tiên của mỗi bộ dữ liệu kiểm tra chứa một số nguyên duy nhất $N$ ($2 \le N \le 10^6$). Dòng tiếp theo của mỗi bộ dữ liệu kiểm tra chứa $N$ số nguyên cách nhau bởi dấu cách $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$). Tổng $N$ trên tất cả các bộ dữ liệu kiểm tra không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu kiểm tra, in ra một dòng chứa một số nguyên: câu trả lời cho bộ dữ liệu đó.

Nhiệm vụ con

Có hai nhiệm vụ con cho bài toán này:

• (30 điểm): Tổng $N$ trên tất cả các bộ dữ liệu kiểm tra không vượt quá $3 \cdot 10^3$.
• (70 điểm): Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

2
5
1 10 1 10 1
5
10 10 10 10 10

Dữ liệu ra 1

32
50

Ghi chú

Trong trường hợp ví dụ đầu tiên, lựa chọn tốt nhất là chọn trung tâm $k = 2$ và cải tạo $h_3$ thành ít nhất $10$, cho phép ba người bạn ở giữa đều mang được $10$ thùng, tổng cộng là $32$.

Trong trường hợp ví dụ thứ hai, không có cải tạo nào có thể làm tăng số lượng thùng chuối, vì vậy câu trả lời là $50$.