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.
import sys
q,w=map(int,sys.stdin.readline().split())
qw=list(map(int,sys.stdin.readline().split()))
b=False
for i in range(w):
    rez=500000
    yt=list(map(int,sys.stdin.readline().split()))
    aw=qw[yt[0]-1:yt[1]]
    for ii in range(1,10):
        if ii in aw:
            chet=aw.count(ii)
            if chet > 1:
                b=True
                q1=aw.index(ii)
                q2=aw.index(ii,q1+1)
                raz=q2-q1
                if raz<rez:
                    rez=raz
                if rez==1:
                    break
                for iii in range(chet-2):
                    q1=q2
                    q2=aw.index(ii,q1+1)
                    raz=q2-q1
                    if raz<rez:
                        rez=raz
                    if rez!=1:
                        continue
                    if rez!=2:
                        continue
    if not b:
        print('-1')
    else:
        print(rez)
        b=False