006 - 日本隆起

問題

$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