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.
class Struct:
	def __init__(self, l, r):
		self.l = l
		self.r = r

def algorithm():
	#try:
		first = input().split(' ')
		n = int(first[0])
		m = int(first[1])
		
		if not(1 <= n <= 500000) or not(1 <= m <= 500000):
			return None
		
		a = input().split(' ')
		
		min = n - 1
		max = 0
		output = [-1 for i in range(0, m)]
		st = list()
		for i in range(0, m):
			rg = input().split(' ')
			l = int(rg[0])  - 1
			r = int(rg[1]) - 1
			if l < min: min = l
			if r > max: max = r
			st.append(Struct(l, r))
			
			if not(0 <= l <= r <= n - 1):
				return None
				
		count = max - min + 1
		i = 0	
		for j in range(1, count):
			for k in range(min, max + 1):
				if k + j >= max + 1:
					break
				if a[k] == a[k + j]: 
					for i in range(0, m):
						if output[i] == -1:
							if (st[i].l <= k <= st[i].r) and (st[i].l <= k + j <= st[i].r):
								output[i] = j
								i += 1
			if i == m:
				break

		for i in range(0, m):
			print(output[i])		
	#except BaseException:
		#return None
		
algorithm()