You are given an array with n integers a_i and m queries. Each query is described by two integers (l_j, r_j).

Let's define the function . The function is defined for only u ≤ v.

For each query print the maximal value of the function f(a_x, a_y) over all l_j ≤ x, y ≤ r_j,  a_x ≤ a_y.

The first line contains two integers n, m (1 ≤ n ≤ 5·10⁴,  1 ≤ m ≤ 5·10³) — the size of the array and the number of the queries.

The second line contains n integers a_i (1 ≤ a_i ≤ 10⁶) — the elements of the array a.

Each of the next m lines contains two integers l_j, r_j (1 ≤ l_j ≤ r_j ≤ n) – the parameters of the j-th query.

For each query print the value a_j on a separate line — the maximal value of the function f(a_x, a_y) over all l_j ≤ x, y ≤ r_j,  a_x ≤ a_y.