Problem Statement

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$. Answer the following $Q$ queries.

• The $i$-th query: You are given integers $L_i$ and $R_i$. Solve the following problem for $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$.
• Divide $B$ into three non-empty contiguous subsequences. For each contiguous subsequence, let us find the maximum value of its elements. Find the minimum possible sum of these maximum values. Here, the constraints of the problem force the length of $B$ to be at least $3$, so there is always at least one way to divide it into three non-empty contiguous subsequences.

Constraints

• $3 \leq N \leq 250000$
• $1 \leq Q \leq 250000$
• $1 \leq A_i \leq 10^8$
• $1 \leq L_i \leq R_i \leq N$
• $R_i - L_i \geq 2$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \cdots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.