No.3017 交互浴
タグ : / 解いたユーザー数 117
作問者 :





問題文
水色コーダーになりたい岩井星人さんは、銭湯へ行って水色の温泉に浸かることにしました。ところが、水色の温泉は熱すぎてずっと浸かっていることができないので、ぬるい緑色の温泉と交互に浸かります。
岩井星人さんは $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か出力せよ。
サンプル
サンプル1
入力
5 7 3 2 4 5
出力
7 4 6 3 7
入浴するたび、岩井星人さんの身体の色は次のように変化していきます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。