Minimum Triangle Sum Query

You are given a sequence \(a\) of length \(n\) and \(q\) queries. Each query is represented by a range \([l, r]\). For each query, find the minimum value of \(a_i+a_j+a_k\) among all triples \((i,j,k)\) such that \(l\le i<j<k\le r\) and the condition \(2\max(a_i,a_j,a_k)<a_i+a_j+a_k\) holds. Note that the inequality \(2\max(a_i,a_j,a_k)a_k\) when the three numbers are arranged in non-decreasing order.

If no such triple exists, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(q\) \((3\le n\le 2000,\ 1\le q\le 1000)\).

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) \((1\le a_i\le10^9)\).

Each of the next \(q\) lines contains two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single line containing the minimum triangle sum \(a_i+a_j+a_k\) that satisfies the condition, or \(-1\) if no valid triple exists.

sample

4 2
1 2 3 4
1 4
2 4

9
9