Lưu vực sông Hồng là một trong những khu vực kinh tế và nông nghiệp quan trọng nhất của Việt Nam. Trải dài từ vùng núi phía Bắc đến đồng bằng Bắc Bộ, con sông không chỉ cung cấp nguồn nước cho sản xuất và sinh hoạt mà còn là tuyến giao thông thủy huyết mạch của hàng triệu người dân.

Tuy nhiên, cùng với tốc độ đô thị hóa và sự biến đổi của khí hậu, những trận mưa lớn xuất hiện với tần suất ngày càng cao đã khiến hệ thống thoát lũ tự nhiên dần trở nên quá tải. Chỉ trong vài giờ, lượng nước khổng lồ từ thượng nguồn có thể tràn về hạ lưu, gây ngập úng trên diện rộng, phá hủy nhiều công trình hạ tầng và ảnh hưởng nghiêm trọng đến đời sống của người dân.

Sau trận đại hồng thủy lịch sử, Chính phủ đã triển khai Dự án Phòng chống lũ Sông Hồng nhằm xây dựng một hệ thống điều tiết nước có khả năng vận hành hoàn toàn tự động. Người được giao phụ trách toàn bộ dự án là anh ~T~, chuyên gia trưởng của Viện Quy hoạch Thủy lợi Quốc gia.

Trong nhiều năm nghiên cứu, anh ~T~ cùng các cộng sự đã khảo sát địa hình trên toàn bộ lưu vực sông Hồng, xây dựng hàng nghìn mô hình mô phỏng mưa lũ và thử nghiệm nhiều phương án điều tiết khác nhau. Sau vô số lần hiệu chỉnh, anh nhận ra rằng thay vì chỉ tập trung xây dựng những con đê cao hơn, việc khai thác chính đặc điểm địa hình tự nhiên để phân phối dòng chảy sẽ mang lại hiệu quả vượt trội trong việc giảm áp lực lũ.

Dọc theo dòng sông Hồng hiện có ~N~ đập chắn nước được xây dựng liên tiếp, đánh số từ ~1~ đến ~N~. Đập thứ ~i~ có chiều cao là ~H_i~.

Để thuận tiện cho việc điều phối, anh ~T~ xây dựng một mạng lưới gồm các hồ điều tiết, mỗi hồ tương ứng với một vùng quản lý được xác định bởi một cặp chỉ số ~[l, r]~ (~1 \le l \le r \le N~), bao phủ toàn bộ các đập từ ~l~ đến ~r~.

Đối với mỗi hồ ~[l, r]~, các chuyên gia xác định một đại lượng gọi là khả năng điều tiết tự nhiên, ký hiệu là ~W(l, r)~. Đại lượng này được định nghĩa là tổng lượng nước lớn nhất có thể đọng lại trên toàn bộ vùng quản lý sau một trận mưa lớn theo đúng quy luật đọng nước tự nhiên.

Trong quá trình tính ~W(l, r)~, nước được giả sử chỉ có thể thoát ra ngoài qua hai đầu của vùng quản lý. Vì vậy, hai đập ở biên của vùng, tức là đập ~l~ và đập ~r~, không bao giờ giữ lại nước phía trên chúng vì nước luôn có thể chảy trực tiếp ra ngoài. Chỉ những đập nằm hoàn toàn giữa hai đầu mút mới có khả năng tích nước. Ví dụ, với vùng có chiều cao ~[1, 2, 0, 3, 4]~, toàn bộ lượng nước chỉ đọng lại trên đập thứ ba, trong khi hai đập ở hai đầu không giữ lại bất kỳ lượng nước nào.

Mỗi hồ điều tiết có nhiệm vụ tiếp nhận, lưu trữ tạm thời và phân phối nước sang các hồ lân cận.

Để giảm chi phí xây dựng và bảo đảm hệ thống luôn vận hành ổn định, hồ quản lý vùng ~[l, r]~ có thể truyền nước trực tiếp sang hồ quản lý vùng ~[l', r']~ nếu đồng thời thỏa mãn các điều kiện sau:

• ~|l - l'| \le 1~;
• ~|r - r'| \le 1~;
• ~(l, r) \neq (l', r')~;
• ~1 \le l' \le r' \le N~.

Mỗi tuyến dẫn xuất phát từ hồ ~[l, r]~ có công suất tối đa bằng ~W(l, r)~ đơn vị nước trong cùng một khoảng thời gian. Các tuyến dẫn hoạt động độc lập với nhau, vì vậy một hồ có thể đồng thời truyền nước qua nhiều tuyến dẫn khác nhau, miễn là lưu lượng trên từng tuyến không vượt quá công suất của chính tuyến dẫn đó.

Để đưa nước vào hệ thống, tất cả các hồ quản lý vùng ~[1, r]~ (~1 \le r \le N~) đều được nối trực tiếp với trạm bơm ở thượng nguồn bằng các tuyến dẫn có công suất không giới hạn. Tương tự, tất cả các hồ quản lý vùng ~[l, N]~ (~1 \le l \le N~) đều được nối trực tiếp tới cửa xả ra biển bằng các tuyến dẫn có công suất không giới hạn.

Trong quá trình vận hành, tất cả các hồ điều tiết và tuyến dẫn đều có thể hoạt động đồng thời. Ngoại trừ trạm bơm ở thượng nguồn và cửa xả ra biển, mọi hồ điều tiết đều phải tuân thủ nguyên tắc bảo toàn lưu lượng, tức là tổng lượng nước chảy vào hồ luôn bằng tổng lượng nước chảy ra khỏi hồ. Đồng thời, lưu lượng truyền trên mỗi tuyến dẫn không được vượt quá công suất của tuyến dẫn đó.

Hãy giúp anh ~T~ xác định lượng nước lớn nhất mà hệ thống phòng chống lũ trên sông Hồng có thể vận chuyển từ thượng nguồn ra biển trong cùng một khoảng thời gian.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương ~Q~.

Mỗi bản thiết kế gồm:

• Dòng đầu tiên chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên không âm ~H_1, H_2, \ldots, H_N~.

Dữ liệu ra

Với mỗi bản thiết kế, in ra một số nguyên duy nhất là lượng nước lớn nhất mà hệ thống có thể vận chuyển.

Ràng buộc

• ~1 \le Q \le 3~.
• ~1 \le N \le 10^6~.
• ~0 \le H_i \le 10^6~.

Ví dụ

Dữ liệu vào:

1
7
10 2 8 1 9 3 7

Dữ liệu ra:

50

Subtask

• Subtask 1 (10%): ~N \le 100~.
• Subtask 2 (20%): ~N \le 1000~.
• Subtask 3 (20%): ~N \le 10^5~.
• Subtask 4 (30%): Không có ràng buộc bổ sung.