A teacher keeps a seating-order roster of a class's most recent quiz scores: one integer percentage score per seat, with seats numbered starting at 0. Across several study-hall review sessions, the teacher repeatedly picks a contiguous block of seats and wants to know how close together the two nearest different scores are within that block — specifically, the smallest absolute difference between any two scores in the block that are not equal to each other. If every score in the chosen block happens to be identical, there is no such pair, and the answer for that block is -1.

Input Format

• Line 1: a single integer n, the number of seats.
• Line 2: n space-separated integers scores[0], scores[1], ..., scores[n-1], the quiz score recorded at each seat.
• Line 3: a single integer q, the number of review-session queries.
• Each of the next q lines contains two integers l r, describing one query: the inclusive seat range [l, r] to examine.

Output Format

Print q lines. On line i, print the minimum absolute difference between two distinct scores among scores[l..r] for the i-th query, or -1 if every score in that range is identical.

Constraints

• 2 <= n <= 100000
• 1 <= scores[i] <= 100
• 1 <= q <= 20000
• 0 <= l < r <= n - 1

6
5 3 5 8 8 2
2
0 3
2 5

2
3

5
6 6 6 9 6
1
0 1

-1