ある宇宙の惑星は地表の大部分が砂漠で、めったに雨が降りません。この惑星に生える植物はすべてサボテンです。雨がとても少ないため、サボテンは互いに協力して水を蓄える方法を進化させました。

惑星のある地域は上下と左右の方向だけを持つ二次元平面です。そこには $N$ 本のサボテンが隙間なく一列に並んでいます。各サボテンの幅は $1$ メートルで、高さは異なっていてもかまいません。環境美化のため、$S$ 番目から $E$ 番目までのサボテンだけを残したところ、十分な雨が降り、サボテンの上で水を蓄えられる領域すべてに水がたまりました。下図のように水がたまります。図中の矢印で示された範囲の外のサボテンは取り除かれたものと考えてください。

サボテンの高さと残すサボテンの範囲が与えられたとき、たまった水の量を面積として求めるプログラムを作成してください。範囲は最大 $Q$ 回与えられます。各範囲は常にすべてのサボテンが存在する初期状態に適用されます。

次の関数を実装してください。

• void init( int H[] )：最初に 1 回だけ呼び出されます。$H$ は左から順にサボテンの高さを格納した大きさ $N$ の配列（ベクトル）です。$N$ はサボテンの本数です。
• int query( int S, int E )：$S$ 番目から $E$ 番目までのサボテンだけを残して十分な雨が降ったとき、たまった水の面積を返してください（$1 \le S \le E \le N$）。最大 $Q$ 回呼び出されます。すべての呼び出しは独立であり、ある呼び出しでサボテンを取り除いても他の呼び出しには影響しません。

実装の詳細

cactus.cpp という名前のファイルをちょうど 1 つ提出してください。このファイルには次の関数が実装されていなければなりません。

• void init( int H[] )
• long long query( int S, int E )

これらの関数は上で説明したとおりに動作しなければなりません。内部で使用する別の関数を定義してもかまいません。提出するコードは入出力を行ったり、他のファイルにアクセスしたりしてはいけません。

採点プログラムの例

提供される採点プログラムは次の形式で入力を読みます。

• 1 行目：$N$, $Q$。
• 次の行：$N$ 個の正の整数。左から順にサボテンの高さを表します。
• 続く $Q$ 行：2 個の正の整数 $S,E$。$S$ 番目から $E$ 番目のサボテンだけを残して雨が降ることを表します（$1 \le S \le E \le N$）。

採点プログラムは、あなたの query() 関数が返した値を 1 行に 1 つずつ出力します。

制約

• $1 \le N \le 500\,000$、$1 \le Q \le 500\,000$。サボテンの高さは $1$ 以上 $10^9$ 以下です。

小課題

小課題 1 (13 点)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

小課題 2 (12 点)

• $1 \le N \le 5\,000$

小課題 3 (22 点)

• サボテンの高さは $20$ 以下です。

小課題 4 (34 点)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

小課題 5 (69 点)

• 元の制約以外に追加の制約はありません。

入出力例

入力 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

注記

上の入力に対するコードの実行例を以下に示します。