P10882 [JRKSJ R9] ZYPRESSEN

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.

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$.

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

### 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.** | $\mathrm{Subtask}$ | $n \le$ | $q \le$ | Special Property | Score | | :-----: | :-----: | :-----: | :-----: | :-----: | | $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$ | 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