The school year is over and Pam's friends are having a party. Her ~N~ classmates each live in a house on a linear street, with houses spaced ~1~ metre apart and numbered from ~1~ to ~N~ from left to right. Each classmate at house ~i~ belongs to a certain friend group ~a_i~. Pam gives you ~Q~ queries where she asks you for the closest distance between any person in friend group ~p_i~ and any person in friend group ~q_i~.

Constraints

In all test cases: ~1 \le p_i, q_i \le N, Q \le 10^5~.

Subtask 1 [20%]

~N, Q \le 3000~

Subtask 2 [80%]

No additional constraints.

Input Specification

First line: ~N~ (the number of people) and ~Q~ (the number of queries).

Second line: ~N~ space-separated numbers describing ~a_i~ for each ~1 \le i \le N~.

The next ~Q~ lines each containing two integers ~p_i~ and ~q_i~ describing the query.

Output Specification

For each of the ~Q~ queries, output the closest distance between any person in friend group ~p_i~ and any person in friend group ~q_i~.

Note: Python users are recommended to use PyPy over classical Python for performance reasons.

Sample Input

6 2
1 2 2 1 3 3
2 3
1 2

Output for Sample Input

2
1

Explanation for Sample Case

For the first query, the distance between friends at houses ~3~ and ~5~ is ~|3 - 5| = 2~, which is the shortest distance between any person in friend group ~2~ and any person in friend group ~3~.