D. Not Japanese Triangle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You encounter a triangle. The first thing you can tell about it is that it is most certainly not Japanese.

The triangle contains $$$n$$$ rows, the $$$i$$$th from top contains $$$i$$$ numbers, $$$a_{i,1}, a_{i,2} \dots a_{i,i}$$$. The numbers are not written in Japanese.

The triangle then speaks to you, but not in Japanese. It wagers $$$100$$$ points that you cannot find the sum of the numbers in each of its rows.

You confidently accept the challenge. But before you begin, the triangle puts on a not Japanese shirt, obscuring all rows from $$$1$$$ to $$$n-1$$$, and only the numbers in row $$$n$$$ remain visible.

Fortunately, the shirt has some not Japanese text that reveals an important property: Every hidden number is the minimum of two numbers directly below it. In other words, $$$a_{i,j} = min(a_{i+1,j}, a_{i+1, j+1})$$$ for all $$$1 \leq i \leq n-1$$$ and $$$1 \leq j \leq i$$$.

Can you find the sum of the not Japanese numbers in each not Japanese row of the not Japanese triangle?

Input

The first line contains one integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$.

The next line contains $$$n$$$ integers $$$a_{n,1}, a_{n,2} \dots a_{n,n}$$$ $$$(1 \leq a_{n,i} \leq 10^9)$$$, the numbers in the $$$n$$$th row of the not Japanese triangle.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-4$$$ satisfy $$$n \leq 5000$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

$$$n$$$ space separated integers, the $$$i$$$th integer representing the sum of the not Japanese numbers in the $$$i$$$th not Japanese row.

Examples
Input
6
1 2 1 2 2 6
Output
1 2 3 5 7 14
Input
11
14 15 20 10 1 16 1 14 5 19 5
Output
1 2 3 4 5 6 7 21 39 58 120
Note

In sample $$$1$$$, the rows are:

Row $$$1$$$: $$$[1]$$$, sum = $$$1$$$.

Row $$$2$$$: $$$[1, 1]$$$, sum = $$$2$$$.

Row $$$3$$$: $$$[1, 1, 1]$$$, sum = $$$3$$$.

Row $$$4$$$: $$$[1, 1, 1, 2]$$$, sum = $$$5$$$.

Row $$$5$$$: $$$[1, 1, 1, 2, 2]$$$, sum = $$$7$$$.

Row $$$6$$$: $$$[1, 2, 1, 2, 2, 6]$$$, sum = $$$14$$$.

—

Problem Idea: culver0412

Problem Preparation: jay_jayjay

Occurrences: Novice K, Advanced D