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 PreparedSequence:
    def __init__(self, seq):
        last_seen = {}  # item -> position
        distances = [-1] * len(seq)
        for i, x in enumerate(seq):
            if x in last_seen:
                distances[last_seen[x]] = i - last_seen[x]
            last_seen[x] = i
        self.distances = distances

    def query(self, l, r):
        return min((d
                for i, d in enumerate(self.distances[l-1:r], l)
                if d != -1 and i + d <= r),
                default=-1)

def test():
    s1 = PreparedSequence([1, 1, 2, 3, 2])
    assert s1.query(1,5) == 1
    assert s1.query(2,4) == -1
    assert s1.query(3,5) == 2

    s2 = PreparedSequence([1,2,1,3,2,3])
    assert s2.query(4,6) == 2
    assert s2.query(1,3) == 2
    assert s2.query(2,5) == 3
    assert s2.query(2,4) == -1
    assert s2.query(1,6) == 2
    print("OK")

if __name__ == '__main__':
    n,m = input().split()
    seq = PreparedSequence(list(map(int, input().split())))
    for _ in range(int(m)):
        l, r = input().split()
        print(seq.query(int(l), int(r)))
