You are given a strip of paper with $n$ cells, where the $i$-th cell has color $a_i$.

Every second, Little A can perform one of the following two operations:

• Paint a cell a certain color.
• Move to an adjacent cell, provided that the color of the current cell and the target cell are the same.

Little A wants to move along the strip, but he does not want to spend too much time, so he will ask you $Q$ questions. The $i$-th question asks for the minimum time required to move from cell $u_i$ to $v_i$.

Note that each question is independent, meaning you do not need to actually modify the colors on the strip.

Input

The first line contains two positive integers $n$ and $Q$, representing the length of the strip and the number of queries, respectively.

The next line contains $n$ positive integers, where the $i$-th number represents the color $a_i$ of the $i$-th cell on the strip.

The next $Q$ lines each contain two positive integers $u_i$ and $v_i$, representing a query for the minimum time in seconds to move from $u_i$ to $v_i$.

Output

Output $Q$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

5 4
2 2 3 1 3
1 5
2 4
5 2
3 3

Output 1

6
4
5
0

Constraints

For $100\%$ of the data, $1 \le u_i, v_i \le n \le 10^6$, $1 \le Q \le 10^6$, and $1 \le a_i \le m \le n$.

• Subtask 1 (3 points): $n \le 10^4$, $Q, m \le 100$.
• Subtask 2 (13 points): $n, Q \le 10^5$, $m \le 3$.
• Subtask 3 (18 points): $n, Q \le 5000$.
• Subtask 4 (66 points): No additional constraints.