## Friend Groups 3

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Java 3.0s
Python 3.5s
Memory limit: 128M

Author:
Problem types

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: .

#### 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.

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 .