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.
from math import sqrt

n, m = map(int, input().split())
strangeconst = (round(sqrt(n)) + 1)
mas = list(map(int, input().split()))
maset = [set() for i in range(strangeconst)]
magic = [-10 ** 10] * strangeconst
for i in range(n):
    if mas[i] in maset[i // strangeconst]:
        magic[i // strangeconst] = mas[i]
    else:
        maset[i // strangeconst].add(mas[i])
for i in range(m):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    strange = set()
    while l <= r:
        if l % strangeconst == 0 and l + strangeconst <= r:
            if magic[l // strangeconst] != - 10 ** 10:
                print(magic[l // strangeconst])
                break
            elif len(strange & maset[l // strangeconst]) >= 1:
                strange &= maset[l // strangeconst]
                print(strange.pop())
                break
            else:
                strange |= magic[l // strangeconst]
                l += strangeconst
        else:
            if mas[l]in strange:
                print(mas[l])
                break
            else:
                strange.add(mas[l])
                l += 1
    if l > r:
        print(-1)
            
        