Minimum Absolute Difference in Subarrays

Given an array A of n integers and q queries, each query specifies a subarray by two indices l and r (1-indexed). For each query, your task is to compute the minimum absolute difference between any two distinct elements in the subarray A[l..r]. If the subarray contains fewer than two elements, output -1.

The answer for each query is defined as follows:

Let \(S = [A_l, A_{l+1}, \dots, A_r]\). If \(|S| < 2\), then the answer is \(-1\); otherwise, if we sort S as \(S' = [s_1, s_2, \dots, s_k]\), then the answer is \[ \min_{1 \le i < k} (s_{i+1} - s_i). \]

You need to process all queries and output the result of each query on a new line.

inputFormat

The input is given via standard input and has the following format:

<n> <q>
<A[1]> <A[2]> ... <A[n]>
<l1> <r1>
<l2> <r2>
... (total q queries)

Here, n is the number of elements in the array, q is the number of queries, and for each query, l and r denote the starting and ending indices of the subarray (1-indexed).

outputFormat

For each query, output an integer which is the minimum absolute difference between any two distinct elements in the specified subarray. If the subarray contains less than 2 elements, output -1. Each answer must be printed on a separate line.

## sample

6 3
3 8 2 5 7 1
1 4
2 5
3 6

1
1
1

</p>