AT_aalc001_o 最小値

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。それぞれのクエリでは整数 $ l,r $ が与えられるので、 \\\[ \\sum\_{l \\leq s \\leq t \\leq r} \\min(A\_s,A\_{s+1},\\ldots,A\_t) \\\] を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ l $ $ r $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ s=t=1 $ の場合だけを考えればよいため、答えは $ 3 $ です。 $ 2 $ 番目のクエリでは、 $ (s,t)=(1,1),(1,2),(2,2) $ の場合の最小値はそれぞれ $ 3,1,1 $ であるため、答えは $ 5 $ です。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^6 $ - $ 1 \leq l \leq r \leq N $ - 入力される数値はすべて整数