Minimal Triangle Perimeter Query

Given a sequence \(a\) of length \(n\) and \(q\) queries, each query provides an interval \([l, r]\). For each query, consider all triplets \(i, j, k\) satisfying \(l \le i < j < k \le r\). A triplet forms a valid triangle with sides \(a_i, a_j, a_k\) (where we assume \(a_i \le a_j \le a_k\)) if and only if \(a_i + a_j > a_k\) (i.e. the triangle inequality holds). Your task is to compute the minimum possible value of \(a_i+a_j+a_k\) among all valid triangles in the specified interval. If no valid triangle exists, output \(-1\).

Note: Indices in the input are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(q\) \((3 \le n \le 10^5, 1 \le q \le 10^5)\).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the sequence.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l < r \le n)\), representing a query.

outputFormat

For each query, output a single integer denoting the minimum triangle perimeter, or \(-1\) if no valid triangle exists.

sample

4 1
2 3 4 5
1 4

9