Problem Statement

Iwai Seijin, who wants to become a light-blue coder, has decided to go to a public bathhouse and soak in the light-blue hot spring. However, the light-blue hot spring is too hot to stay in continuously, so he alternates it with the lukewarm green hot spring.

Iwai Seijin takes $N$ baths, soaking in the light-blue hot spring on odd-numbered baths and in the green hot spring on even-numbered baths.
For each $i\ (1 \leq i \leq N)$, when the $i$-th bath is finished, the part of Iwai Seijin's body up to $H_i$ cm from his feet becomes the same color as the hot spring he soaked in.

Iwai Seijin's height is greater than $\max_{1 \leq i \leq N} {H_i}$ cm, and before bathing, his whole body is green. For each $i\ (1 \leq i \leq N)$, find the total length in cm of the part of Iwai Seijin's body that is light blue when the $i$-th bath is finished.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq H_i \leq 10 ^ 9$
• All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$H_1\ H_2\ \dots H_N$

Output

Print $N$ lines. On the $i$-th line, print the total length in cm of the part of Iwai Seijin's body that is light blue when the $i$-th bath is finished.

Sample

5
7 3 2 4 5

7
4
6
3
7