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.
dl_posl, kol_zapr = map(int, input().split(" "))
spisok = list(map(int, input().split(" ")))
sp = []

for i in range(kol_zapr):
    l, r = map(int, input().split(" "))
    temp_list = {}
    for n, j in enumerate(spisok[l-1:r]):
        if j not in temp_list:
            temp_list[j] = [l-1+n]
        else:
            temp_list[j].append(l-1+n)
    for b in list(temp_list):
        if len(temp_list[b])<2:
            del temp_list[b]
        elif len(temp_list[b]) == 2:
            temp_list[b] = temp_list[b][1]-temp_list[b][0]
        else:
            m=999999
            for c in range(len(temp_list[b][1:])):
                if temp_list[b][c+1]-temp_list[b][c]<m:
                    m = temp_list[b][c+1]-temp_list[b][c]
            temp_list[b]=m
    try:
        sp.append(min(temp_list.values()))
    except:
        sp.append(-1)

for a in sp:
    print(a)