不一样的询问¶

题目背景¶

zheha觉得询问最大值太单调了，他想换一个询问方式

给出一个包含\(n\)个正整数的序列\(a\),

定义一个区间\([l,r]\)的权值为 \(本区间内所有数的最大值+a[l]\)。

然后给出\(q\)个询问。

对于每一个询问给出\(l\)和\(r\),求\([l,r],[l+1,r]……[r,r]\)这些区间的权值的最小值。

第一行\(n\)和\(q\)，用空格隔开。

第二行\(n\)个数，代表\(a\)序列。

接下来\(q\)行，每行\(l\)和\(r\),代表询问。

\(q\)行代表询问的答案。

10 15
206 979 243 496 606 392 480 571 678 762 
10 10
10 10
8 9
3 5
1 6
4 4
1 8
8 8
2 7
3 4
1 3
2 6
10 10
3 8
10 10

\(n,q\le 250000\)

\(1\le a_i\le10^9\)