Tổng từng cặp đối xứng (Sums of Symmetric Pairs)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên $a_0,a_1,\ldots,a_{n-1}$. Đặt

Với mỗi $0\le i<k$, tạo

Nếu $n$ lẻ, phần tử giữa không có phần tử đối xứng khác; trong phiên bản PHOJ này ta giữ nguyên nó:

Vì vậy độ dài mảng kết quả là

Hãy in $b_0,b_1,\ldots,b_{m-1}$.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In $m=\lceil n/2\rceil$ số nguyên của mảng $b$ trên một dòng.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $|a_i|\le10^3$.

Subtask 2 (30 điểm): $1\le n\le5000$, $|a_i|\le10^6$.

Subtask 3 (50 điểm): $1\le n\le2\cdot10^5$, $|a_i|\le10^9$.

Ví dụ

Input

7
2 5 -1 8 4 9 3

Output

5 14 3 8

Giải thích

$b_0=2+3=5$, $b_1=5+9=14$, $b_2=-1+4=3$. Vì $n=7$ lẻ nên giữ nguyên phần tử giữa $a_3=8$.