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.
def compare(pair1, pair2):
    if pair1[1] < pair2[1]:
        return -1
    elif pair1[1] > pair2[1]:
        return 1
    elif pair1[0] < pair2[0]:
        return -1
    elif pair1[0] > pair2[0]:
        return 1
    else:
        return 0


def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K(object):
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K


def check_index(i, left, right):
    return left <= i and i <= right

with open("input.txt") as inputFile:
    # Read sizes
    arraySize, requestsCount = (int(s) for s in inputFile.readline().split())
    # print(arraySize, requestsCount)

    # Read array
    array = [int(s) for s in inputFile.readline().split()]
    array_with_indices=[]
    for idx, val in enumerate(array):
        array_with_indices.append((idx+1, val))

    # print(array)
    # print(array_with_indices)

    # Sort array
    array_with_indices = sorted(array_with_indices, key = cmp_to_key(compare))
    #array_with_indices.sort(cmp=compare)

    print(array_with_indices)

    # Main loop by requestsd
    for i in range(0, requestsCount):
        left, right = (int(s) for s in inputFile.readline().split())

        min_distance = float('inf')
        cur_distance = -1
        current_value = None
        first_index = 0
        for pair in array_with_indices:
            if current_value != pair[1]:
                # We have new value
                if cur_distance < min_distance and cur_distance != -1:
                    min_distance = cur_distance

                current_value = pair[1]
                first_index = 0
                if check_index(pair[0], left, right):
                    first_index = pair[0]
            else:
                if check_index(pair[0], left, right):
                    if first_index == 0:
                        first_index = pair[0]
                    else:
                        cur_distance = pair[0] - first_index;
        if cur_distance < min_distance and cur_distance != -1:
            min_distance = cur_distance
        print(min_distance if min_distance != float('inf') else -1)


