Background

The atmosphere is becoming clearer and clearer.
Silent cypresses stand straight up into the sky.

Under the dazzling sky,
sorrow is still deep green.
Cypress trees sway quietly.
Birds once again cut through the blue sky.
There are no sincere words left here.
Asura’s tears fall like rain onto the soil.

Problem Description

It is already completely autumn.

Even so, cypresses (ZYPRESSEN) are probably as dark as ever.

You are given a sequence $a$ of length $n$. There are $q$ queries, each query is as follows:

• You are given an interval $[l, r]$. For all $i, j, k$ satisfying $l \le i < j < k \le r$, if a triangle with side lengths $a_i, a_j, a_k$ exists, you need to find the minimum value of $a_i + a_j + a_k$.

When the three side lengths are $a, b, c$ $(a \le b \le c)$, they can form a triangle if and only if $a + b > c$.

Input Format

The first line contains two integers $n, q$.

The second line contains $n$ integers $a_{1\dots n}$.

The next $q$ lines each contain two integers $l, r$, representing a query.

Output Format

Output $q$ lines, one integer per line representing the answer. If there is no valid $i, j, k$, output 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

Hint

Sample Explanation 1

For the interval $[3, 5]$, since $1 + 5 < 12$, there is no valid triangle.

For the intervals $[2, 5]$ and $[2, 6]$, choose $a_i = 11, a_j = 5, a_k = 12$.

For the interval $[1, 7]$, choose $a_i = 3, a_j = 11, a_k = 10$.

Constraints

This problem uses bundled testdata.

Special Property: it is guaranteed that $a_i$ is generated uniformly at random within the range.

For all testdata, it is guaranteed that $1 \le n \le 2.5 \times 10^5$, $1 \le q \le 5 \times 10^5$, $1 \le a_i \le 10^7$, and $1 \le l \le r \le n$.

Translated by ChatGPT 5