Cho một mảng gồm các số nguyên không âm $s_1, \dots, s_n$ với $n \ge 3$, ta gọi một dãy gồm $n$ số không âm (không nhất thiết là số nguyên) $x_1, x_2, \dots, x_n$ là cân bằng nếu với mỗi $i$, điều kiện $x_i + x_{i+1} \le s_i$ được thỏa mãn, trong đó $x_{n+1} = x_1$.

Gọi $f(s_1, s_2, \dots, s_n)$ là giá trị lớn nhất của $x_1 + x_2 + \dots + x_n$ trong tất cả các cấu hình trọng số cân bằng.

Bạn được cho một mảng gồm các số nguyên không âm $a_1, a_2, \dots, a_n$.

Hãy tìm $n - 2$ số: $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($3 \le n \le 100\,000$).

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$).

Dữ liệu ra

In ra $n - 2$ số: $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$.

Câu trả lời của bạn sẽ được coi là đúng nếu sai số tương đối hoặc tuyệt đối của tất cả các giá trị không vượt quá $10^{-9}$.

Ví dụ

Dữ liệu vào 1

4
20 20 20 15

Dữ liệu ra 1

30.0 35

Ghi chú

Trong ví dụ đầu tiên, đối với tiền tố gồm ba phần tử, chúng ta có thể đặt các giá trị $\{10, 10, 10\}$, đối với tiền tố tiếp theo, chúng ta có thể đặt các giá trị $\{10.1, 9.9, 10.1, 4.9\}$.

Dữ liệu vào 2

6
1 2 1 2 1 2

Dữ liệu ra 2

2 2 3 3

Dữ liệu vào 3

12
1 1 1 3 1 1 2 5 3 2 1 2

Dữ liệu ra 3

1.5 2 3 3 4 5 8 8 9 9