問題文

水色コーダーになりたい岩井星人さんは、銭湯へ行って水色の温泉に浸かることにしました。ところが、水色の温泉は熱すぎてずっと浸かっていることができないので、ぬるい緑色の温泉と交互に浸かります。

岩井星人さんは $N$ 回の入浴を行い、奇数回目の入浴では水色の温泉に、偶数回目の入浴では緑色の温泉に浸かります。
各 $i\ (1 \leq i \leq N)$ について、$i$ 回目の入浴を終えた時点で、岩井星人さんの身体の足元から $H_i$ cmが浸かった温泉と同じ色になります。

岩井星人さんの身長は $\max_{1 \leq i \leq N} {H_i}$ cmよりも大きく、入浴前、岩井星人さんの身体は全身が緑色です。各 $i\ (1 \leq i \leq N)$ について、$i$ 回目の入浴を終えた時点で、岩井星人さんの身体のうち水色になっている部分は全部で何cmか答えてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq H_i \leq 10 ^ 9$
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$N$ 行出力せよ。$i$ 行目には、$i$ 回目の入浴を終えた時点で、岩井星人さんの身体のうち水色になっている部分が全部で何cmか出力せよ。

サンプル

5
7 3 2 4 5

7
4
6
3
7