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.
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
		
		arr = input().split(' ')
		a = [int(arr[i]) for i in range(0, n)]
		del arr
		
		output = list()
		for i in range(0, m):
			rg = input().split(' ')
			l = int(rg[0]) - 1
			r = int(rg[1])
			
			if not(1 <= l + 1 <= r <= n):
				return None
			
			count = r - l + 1
			result = count
			x = a[l : r]
			d = {i : x[i] for i in range(0, count - 1)}
			r = list(d.items())
			r.sort(key = lambda item: item[1])
			for i in range(0, count - 2):
				if r[i][1] == r[i + 1][1]:
					val = r[i + 1][0] - r[i][0]
					if val < result:
						result = val
			
			if not result == count:
				output.append(result)
			else:
				output.append(-1)			

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