問題
$N$個の島が1列に並んでいて、左から順に、$1,2,...,N$と番号が振られています。
$i$番の島は最初、標高は$A_i$です。
これから、$Q$回のイベントが起こります。$i$回目のイベントの内容は以下の通りです。
・$L_i$番から$R_i$番までの島の高さが$C_i$あがる。
島のでこぼこ度を以下のように定義します。
・全ての隣り合っている島における「標高の差の絶対値」の総和
各イベントの後の島のでこぼこ度を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ ... $A_N$ $Q$ $L_1$ $R_1$ $C_1$ $L_2$ $R_2$ $C_2$ ... $L_Q$ $R_Q$ $C_Q$
1行目に整数$N$が与えられる。
2行目に整数列$A$が与えられる。
3行目に整数$Q$が与えられる。
4行目から$Q$行にわたって整数$L,R,C$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,Q \leq 10^{5}$
- $1 \leq A_i \leq 2×10^{5} (1 \leq i \leq N)$
- $1 \leq L_i < R_i \leq N (1 \leq i \leq Q)$
- $1 \leq C_i \leq 2×10^{5} (1 \leq i \leq Q)$
30%の部分点を獲得できる入出力ケースについて以下を満たす。
- $1 \leq N,Q \leq 10^{3}$
- $1 \leq A_i \leq 2×10^{3} (1 \leq i \leq N)$
- $1 \leq C_i \leq 2×10^{3} (1 \leq i \leq Q)$
入出力例
入力例1
5 1 1 1 1 1 3 1 3 1 3 5 1 3 3 1
出力例1
1 2 4
最初の島の状態は[1,1,1,1,1]です。
1つ目のイベントの後、島の状態は[2,2,2,1,1]です。
この時、3番と4番の島の標高の差の絶対値は1です。また、他のすべての隣り合った島の標高の差の絶対値は0なので、総和は1です。
2つ目のイベントの後、島の状態は[2,2,3,2,2]です。
この時、2番と3番、3番と4番の島の標高の差の絶対値はそれぞれ1です。また、他のすべての隣り合った島の標高の差の絶対値は0なので、総和は2です。
3つ目のイベントの後、島の状態は[2,2,4,2,2]です。
この時、2番と3番、3番と4番の島の標高の差の絶対値はそれぞれ2です。また、他のすべての隣り合った島の標高の差の絶対値は0なので、総和は4です。
入力例2
5 1 3 1 7 3 3 1 3 2 4 5 1 1 4 5
出力例2
12 13 18