JOI and IOI are twins. JOI has recently taken an interest in baking, and today he baked a cake. However, IOI smelled it and arrived just as it was finished, so they decided to share the cake.

The cake is circular. It is cut radially into $N$ pieces, which are numbered 1 to $N$ in counter-clockwise order. That is, for $1 \le i \le N$, the $i$-th piece is adjacent to the $(i-1)$-th and $(i+1)$-th pieces (where the 0-th piece is considered the $N$-th piece, and the $(N+1)$-th piece is considered the 1st piece). The size of the $i$-th piece is $A_i$, and since the cutting was done poorly, all $A_i$ are distinct.

Figure 1: Example of a cake ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 9$)

They decided to divide the $N$ pieces between JOI and IOI as follows:

• First, JOI chooses and takes one of the $N$ pieces.
• After that, starting with IOI, IOI and JOI take turns picking one of the remaining pieces. However, (since they are both bad at picking pieces without breaking the cake) they can only pick a piece if at least one of its two adjacent pieces has already been taken. If there are multiple such pieces available, they choose the largest one.

JOI wants to know, for each piece, what the total size of the pieces he will eventually obtain would be if he chooses that piece first.

Input

Read the following from standard input:

• The first line contains an integer $N$, representing that the cake is cut into $N$ pieces.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $A_i$, representing the size of the $i$-th piece.

Output

Output $N$ lines to standard output. The $i$-th line ($1 \le i \le N$) should contain a single integer representing the total size of the pieces JOI will eventually obtain if he chooses the $i$-th piece first.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 300\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subtasks

Subtask 1 [10 points]

• $N \le 5\,000$ is satisfied.

Subtask 2 [90 points]

• There are no additional constraints.

Examples

Input 1

5
2
8
1
10
9

Output 1

13
18
12
13
12

Note

This example corresponds to the figure in the problem description. For example, suppose the 1st piece is chosen first. In this case:

• Among the remaining pieces, the pieces whose "at least one of the adjacent pieces has already been taken" are the 2nd and 5th pieces. Since the 5th piece is larger, the 5th piece is taken next.
• Similarly, comparing the 2nd and 4th pieces next, the 4th piece is larger, so the 4th piece is taken.
• Next, comparing the 2nd and 3rd pieces, the 2nd piece is larger, so the 2nd piece is taken.
• Finally, only the 3rd piece remains, so the 3rd piece is taken.

Thus, the order in which the pieces are taken is: 1st (2) $\to$ 5th (9) $\to$ 4th (10) $\to$ 2nd (8) $\to$ 3rd (1) (The values in parentheses are the sizes of the pieces)

The pieces JOI takes are the 1st, 4th, and 3rd pieces. Their total size is 13, so 13 is output on the first line. The same calculation is performed for cases where a piece other than the 1st is chosen first.