There are N students in a round table meeting. Each student belongs to a university given in the array \(A[i]\), which denotes the university that the \(i^{th}\) student belongs to.
There are Q queries of the form \(x\; y\), denoting two universities. The answer to each query is the minimum time taken by any one of the student from these universities to meet each other.

Note:

Exactly 1 student of university x and y have to meet each other
In this context, meeting means that the absolute distance between the positions is \(\le 1\)
Time taken by the student to move from \(i^{th}\) position to \(i+1^{th}\) or \(i-1^{th}\) position is exactly 1 second
Both the students move together at the same time
Both the students move optimally in the correct direction
Two students can belong to the same university
Round Table means that the nth position and 1st position are adjacent

Input

The first line of input contains 2 integers N and Q

The second line contains N space seperated integers denoting \(A[i]\)

Q lines follow . Each containing 2 integers x and y

Output

The output contains q lines each containing the answer to each query

CONSTRAINTS

Constraint: \(1 \le N \le 50000\) , \(1 \le Q \le 100\) The elements of the array are between 1 to \(100000\)

x and y are guaranteed to be present in the array