JOI và IOI là hai anh em sinh đôi. JOI vừa nướng xong một chiếc bánh thì IOI ngửi thấy mùi thơm và chạy đến, nên hai người quyết định chia bánh.

Chiếc bánh có dạng hình tròn. JOI cắt bánh bằng các đường xuất phát từ một điểm, tạo thành \(N\) miếng, rồi đánh số các miếng từ \(1\) đến \(N\) theo chiều ngược kim đồng hồ. Miếng \(i\) kề với miếng \(i-1\) và miếng \(i+1\), trong đó miếng \(0\) được hiểu là miếng \(N\), còn miếng \(N+1\) được hiểu là miếng \(1\). Kích thước miếng \(i\) là \(A_i\). Các giá trị \(A_i\) đôi một khác nhau.

Hai người lấy bánh theo các quy tắc sau:

• Đầu tiên, JOI được chọn một miếng bất kỳ trong \(N\) miếng.
• Sau đó, bắt đầu từ IOI, hai người luân phiên lấy mỗi lượt một miếng còn lại cho đến khi hết bánh.
• Trong mỗi lượt sau lượt đầu tiên, chỉ được lấy một miếng có ít nhất một trong hai miếng kề nó đã được lấy. Nếu có nhiều miếng như vậy, người đang đến lượt phải lấy miếng lớn nhất. Quy tắc này áp dụng cho cả JOI và IOI.

Yêu cầu

Với từng miếng bánh, hãy tính tổng kích thước các miếng JOI nhận được nếu chọn miếng đó ở lượt đầu tiên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(A_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(i\) chứa tổng kích thước các miếng JOI nhận được nếu lấy miếng \(i\) đầu tiên.

Giới hạn

• \(2 \le N \le 300\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• Các giá trị \(A_i\) đôi một khác nhau.
• Thời gian: 1,5 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 5\,000\).
• Bài toán con 2 (90 điểm): Không có giới hạn bổ sung.

Ví dụ

5
2
8
1
10
9

13
18
12
13
12

Nếu JOI lấy miếng \(1\) đầu tiên, các lượt tiếp theo diễn ra như sau:

• IOI có thể lấy miếng \(2\) hoặc \(5\) và phải chọn miếng \(5\) vì \(9 > 8\).
• JOI có thể lấy miếng \(2\) hoặc \(4\) và phải chọn miếng \(4\) vì \(10 > 8\).
• IOI có thể lấy miếng \(2\) hoặc \(3\) và phải chọn miếng \(2\) vì \(8 > 1\).
• JOI lấy miếng \(3\) còn lại.

Thứ tự lấy các miếng là \(1,5,4,2,3\). JOI nhận các miếng \(1,4,3\), có tổng kích thước \(2+10+1=13\).