题目背景

大气层越发清澈澄明
无声的丝柏冲天而立

黄金般的草地
走来一个人影
农夫身穿蓑衣
正在定睛看我
却不知他是否
真的能看见我
耀眼的大气下
哀怨依然青深
柏木静静摇曳
鸟儿再次划破青空
此处已无真心话语
阿修罗泪如雨落土

重振精神仰头呼吸
微白的肺越发紧缩
任凭身体散作空中微尘
银杏枝头再次发光
柏木愈发黑沉
云之花火纷飞坠落

——宫泽贤治《春与阿修罗》

题目描述

给你一个长度为 $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$			$10$
$2$	$5\times 10^4$			$25$
$3$	$2.5\times 10^5$	$5\times 10^5$	$\checkmark$	$10$
$4$				$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$。