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.
try:
  xrange
except NameError:
  xrange = range


class SegmentTree(object):
  def __init__(self, n):
    self.n = n
    self.N = 2 * n + 1
    self.a = [10**9 for i in xrange(0, self.N)]

  def put(self, pos, val):
    pos += self.n - 1
    while pos > 0:
      self.a[pos] = min(self.a[pos], val)
      pos //= 2

  def get(self, l, r):
    l += self.n - 1
    r += self.n - 1
    al = self.a[l]
    ar = self.a[r]
    while r > l + 1:
      if l % 2 == 0:
        al = min(al, self.a[l + 1])
      if r % 2 == 1:
        ar = min(ar, self.a[r - 1])
      l //= 2
      r //= 2
    return min(al, ar)

#n, m = [int(x) for x in raw_input().split()]
#a = [int(x) for x in raw_input().split()]
n, m = map(int, input().split())
a = list(map(int, input().split()))

prev = [-1 for i in xrange(0, len(a))]
prev_map = {}
for i in xrange(0, len(a)):
  if a[i] in prev_map:
    prev[i] = prev_map[a[i]]
  prev_map[a[i]] = i

queries = []
for i in range(m):
  #l, r = [int(x) for x in raw_input().split()]
  l, r = list(map(int, input().split()))
  queries.append((r - 1, l - 1, i))

queries = sorted(queries)
tree = SegmentTree(2 ** 20)
R = -1
res = [None for i in xrange(0, m)]
for (r, l, ind) in queries:
  for i in xrange(R + 1, r + 1):
    if prev[i] != -1:
      tree.put(prev[i] + 1, i - prev[i])
  R = r
  val = tree.get(l + 1, r + 1)
  if val == 10**9:
    val = -1
  res[ind] = val
print('\n'.join(str(val) for val in res))

