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