Problem
チュバティはグリゴリー・メレホフに、サーベルでバクラン攻撃を行う方法を教えています。ターゲットとして、1 から n まで番号が付けられた n ツリーを連続して使用します。チュバティは、すべての木の強さを自然数で推定し、それらを書き留めました。メレホフが切ることができた木ごとに、彼は木に書かれた数と同じ数のポイントを受け取り、できなかった場合は同じ量を失います.
チュバティはグリゴリーに、l から r までの木を番号の昇順で打つように頼みます。メレホフは最近肩を痛めたので、1 回おきに木を切り倒すことができます。つまり、i 番の木を切り倒した場合、i 番の木を切り倒すことはできません。 code>i + 1 ですが、番号 i + 2 などで木を切り倒すことができます。
Chubat
m はかつて Grigory に打撃を与えるように頼んだことがありますが、彼は Melekhov がどの木を伐採できるかを忘れていました。グレゴリーが各試行で獲得したポイント数を判断するのを手伝ってください。
入力
最初の行には、2 つの数字 n と m が含まれています (\(1 <= n, m <= 100000 \))
2 行目には n 個の数字が含まれます - すべての木の強さです。ここで、木の強さ i は位置 i に書かれています。
次の m 行には、数値 l と r のペアが含まれています (\(1 < ; = l <= r <= n\))、チュバティが伐採を依頼した木を意味します。
出力
各クエリについて、グリゴリーがこの試みで獲得したポイント数を出力してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|