AT_aalc001_o 最小値

You are given a sequence of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Process $ Q $ queries. In each query, you are given integers $ l,r $ . Find \\\[ \\sum\_{l \\leq s \\leq t \\leq r} \\min(A\_s,A\_{s+1},\\ldots,A\_t) \\\]

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in the following format: > $ l $ $ r $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 For query $ 1 $ , only the case $ s=t=1 $ needs to be considered, so the answer is $ 3 $ . For query $ 2 $ , the minimum values for $ (s,t)=(1,1),(1,2),(2,2) $ are $ 3,1,1 $ , respectively, so the answer is $ 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 $ - All numerical values in the input are integers.