[JRKSJ R9] ZYPRESSEN

大气层越发清澈澄明\ 无声的丝柏冲天而立  黄金般的草地\ 走来一个人影\ 农夫身穿蓑衣\ 正在定睛看我\ 却不知他是否\ 真的能看见我\ 耀眼的大气下\ 哀怨依然青深\ 柏木静静摇曳\ 鸟儿再次划破青空\ 此处已无真心话语\ 阿修罗泪如雨落土 重振精神仰头呼吸\ 微白的肺越发紧缩\ 任凭身体散作空中微尘\ 银杏枝头再次发光\ 柏木愈发黑沉\ 云之花火纷飞坠落 ——宫泽贤治《春与阿修罗》

给你一个长度为 $n$ 的序列 $a$，共有 $q$ 次询问，每次询问如下： * 给你一个区间 $[l,r]$，对于所有的 $i,j,k$ 满足 $l\le i<j<k\le r$ 且三边长度分别为 $a_i,a_j,a_k$ 的三角形存在，你需要求出 $a_i+a_j+a_k$ 的最小值。 三边长度分别为 $a,b,c(a\le b\le c)$ 时，能构成三角形当且仅当 $a+b>c$。

第一行两个整数 $n,q$。 第二行 $n$ 个整数 $a_{1\dots n}$。 接下来 $q$ 行，每行两个整数 $l,r$ 表示询问。

$q$ 行，每行一个整数表示答案。如果不存在符合条件的 $i,j,k$，输出 `yumi!`。

7 6
3 11 1 5 12 19 10
1 1
3 5
2 5
1 7
2 6
1 4

yumi!
yumi!
28
24
28
yumi!

20 20
26 17 11 89 56 33 72 73 43 77 80 87 97 17 43 74 72 91 49 69
10 19
2 4
3 5
2 11
1 12
10 19
3 5
8 15
8 12
14 20
5 11
13 18
2 18
17 19
1 9
5 8
9 12
1 11
4 13
3 18

109
yumi!
yumi!
87
54
109
yumi!
103
193
109
132
163
45
212
54
161
200
54
132
87

### 样例解释 1 对于区间 $[3,5]$，因为 $1+5<12$，所以不存在合法的三角形。 对于区间 $[2,5]$ 和 $[2,6]$，选取 $a_i=11,a_j=5,a_k=12$。 对于区间 $[1,7]$，选取 $a_i=3,a_j=11,a_k=10$。 ### 数据规模与约定 **本题采用捆绑测试。** | $\mathrm{Subtask}$ | $n\le$ | $q\le$ | 特殊性质 |分数 | | :-----: | :-----: | :-----: | :-----: | :-----: | | $1$ | $5\times 10^3$ | $5\times 10^3$ | |$10$ | | $2$ | $5\times 10^4$ | $5\times 10^4$ | |$25$ | | $3$ | $2.5\times 10^5$ | $5\times 10^5$ | $\checkmark$|$10$ | | $4$ | $2.5\times 10^5$ | $5\times 10^5$ | |$55$ | 特殊性质：保证 $a_i$ 在范围内等概率随机生成。 对于所有数据，保证 $1\le n\le 2.5\times 10^5$，$1\le q\le 5\times 10^5$，$1\le a_i\le 10^7$，$1\le l\le r\le n$。