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

#### Constraints

In all test cases: .

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

#### Input Specification

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

Second line: space-separated numbers describing for each .

The next lines each containing two integers and describing the query.

#### Output Specification

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

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 and is , which is the shortest distance between any person in friend group and any person in friend group .

## Comments