You are given sequence a_1, a_2, ..., a_{n} and m queries l_{j}, r_{j} (1 ≤ l_{j} ≤ r_{j} ≤ n). For each query you need to print the minimum distance between such pair of elements a_{x} and a_{y} (x ≠ y), that:  both indexes of the elements lie within range [l_{j}, r_{j}], that is, l_{j} ≤ x, y ≤ r_{j};  the values of the elements are equal, that is a_{x} = a_{y}. 

The text above understands distance as |x - y|.


-----Input-----

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·10^5) — the length of the sequence and the number of queries, correspondingly. 

The second line contains the sequence of integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9). 

Next m lines contain the queries, one per line. Each query is given by a pair of numbers l_{j}, r_{j} (1 ≤ l_{j} ≤ r_{j} ≤ n) — the indexes of the query range limits.


-----Output-----

Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.


-----Examples-----
Input
5 3
1 1 2 3 2
1 5
2 4
3 5

Output
1
-1
2

Input
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6

Output
2
2
3
-1
2

Source: codeforces | Difficulty: HARD
Tags: Data structures


Solutions:
import sys

class Fenwick(object):

	def __init__(self, n):
		self.n = n
		self.a = [10 ** 9 for i in range(n)]
		self.w = 10 ** 9

	def zag(self, i, zn):
		self.w = min(self.w, zn)
		while i < self.n:
			self.a[i] = min(self.a[i], zn)
			i = i | i + 1

	def pol(self, r):
		ans = 10 ** 9
		while r >= 0:
			if ans > self.a[r]:
				ans = self.a[r]
			if ans == self.w:
				break
			r = (r & r + 1) - 1
		return ans
(n, m) = [int(x) for x in sys.stdin.readline().split()]
a = [int(x) for x in sys.stdin.readline().split()]
nd = [-1 for i in range(0, len(a))]
vi = {}
for i in range(0, len(a)):
	if a[i] in vi:
		nd[i] = vi[a[i]]
	vi[a[i]] = i
inp = sys.stdin.readlines()
och = [[] for i in range(n)]
for i in range(m):
	(l, r) = inp[i].split()
	och[int(r) - 1].append((int(l) - 1, i))
der = Fenwick(2 ** 19)
ans = [None for i in range(0, m)]
le = -1
for r in range(n):
	if nd[r] != -1:
		der.zag(500000 - nd[r] + 1, r - nd[r])
		le = max(le, nd[r])
	for (l, ind) in och[r]:
		if l > le:
			ans[ind] = -1
			continue
		zn = der.pol(500000 - l + 1)
		if zn == 10 ** 9:
			zn = -1
		ans[ind] = zn
print('\n'.join((str(zn) for zn in ans)))