You are given sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* queries *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*). For each query you need to print the minimum distance between such pair of elements *a*<sub class="lower-index">*x*</sub> and *a*<sub class="lower-index">*y*</sub> (*x* ≠ *y*), that:
 -  both indexes of the elements lie within range [*l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub>], that is, *l*<sub class="lower-index">*j*</sub> ≤ *x*, *y* ≤ *r*<sub class="lower-index">*j*</sub>; -  the values of the elements are equal, that is *a*<sub class="lower-index">*x*</sub> = *a*<sub class="lower-index">*y*</sub>. 
The text above understands distance as |*x* - *y*|.
The first line of the input contains a pair of integers *n*, *m* (1 ≤ *n*, *m* ≤ 5·10<sup class="upper-index">5</sup>) — the length of the sequence and the number of queries, correspondingly. 

The second line contains the sequence of integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> ( - 10<sup class="upper-index">9</sup> ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). 

Next *m* lines contain the queries, one per line. Each query is given by a pair of numbers *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*) — the indexes of the query range limits.
from bisect import bisect_left
import sys

n, m = (int(x) for x in input().split())

def read_number():
	n = 0
	while True:
		c = sys.stdin.read(1)
		if c == " ":
			return (n, False)
		elif c == "\n":
			return (n, True)
		n *= 10
		n += int(c)

numbers = []

numbers_prev = {}

inf = float("inf")

for i in range(500000):
	v, break_after = read_number()
	if v not in numbers_prev:
		numbers.append((v, inf))
	else:
		numbers.append((v, i - numbers_prev[v]))
	numbers_prev[v] = i
	if break_after:
		break

for i in range(m):
	l, r = (int(x) for x in input().split())
	min_length = None
	for j in range(l, r):
		if numbers[j][1] != inf and j - numbers[j][1] >= l - 1:
			if min_length is None or min_length > numbers[j][1]:
				min_length = numbers[j][1]
	print(min_length or "-1")
