You are given sequence a 1, a 2, …, a n and m queries l j, r j (1 ≤ l j ≤ r j ≤ n). For each query you need to print the minimum distance between such pair of elements a x and a y ( x ≠ y), that:
- both indexes of the elements lie within range [ l j, r j], that is, l j ≤ x, y ≤ r j;
- the values of the elements are equal, that is a x = a y.
The text above understands distance as |x - y|.
Input
The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.
The second line contains the sequence of integers a 1, a 2, …, a n ( - 109 ≤ a i ≤ 109).
Next m lines contain the queries, one per line. Each query is given by a pair of numbers l j, r j (1 ≤ l j ≤ r j ≤ n) — the indexes of the query range limits.
Output
Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.
Examples
input
5 3
1 1 2 3 2
1 5
2 4
3 5
output
1
-1
2
input
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
output
2
2
3
-1
2
Solution:
import java.io.Reader; import java.util.Arrays; import java.util.InputMismatchException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Random; import java.io.BufferedReader; import java.util.List; import java.io.OutputStream; import java.util.Comparator; import java.io.PrintWriter; import java.io.Writer; import java.io.IOException; /** * Built using CHelper plug-in * Actual solution is at the top * @author Niyaz Nigmatullin */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastScanner in = new FastScanner(inputStream); FastPrinter out = new FastPrinter(outputStream); TaskD solver = new TaskD(); solver.solve(1, in, out); out.close(); } } class TaskD { static class Query { int left; int right; int answer; public Query(int left, int right) { this.left = left; this.right = right; } } public void solve(int testNumber, FastScanner in, FastPrinter out) { int n = in.nextInt(); int m = in.nextInt(); int[] a = in.readIntArray(n); Query[] q = new Query[m]; for (int i = 0; i < m; i++) { q[i] = new Query(in.nextInt() - 1, in.nextInt()); } Query[] sortedQ = q.clone(); Arrays.sort(sortedQ, new Comparator<Query>() { public int compare(Query o1, Query o2) { return Integer.compare(o1.left, o2.left); } }); int[] as = ArrayUtils.sortAndUnique(a); for (int i = 0; i < a.length; i++) { a[i] = Arrays.binarySearch(as, a[i]); } int[] last = new int[as.length]; Arrays.fill(last, -1); FenwickMin f = new FenwickMin(n); int currentQuery = m - 1; for (int i = n - 1; i >= 0; i--) { int x = a[i]; if (last[x] >= 0) { f.setAndMin(last[x], last[x] - i); } last[x] = i; while (currentQuery >= 0 && sortedQ[currentQuery].left == i) { sortedQ[currentQuery].answer = f.getMin(sortedQ[currentQuery].right - 1); --currentQuery; } } for (Query e : q) { if (e.answer == Integer.MAX_VALUE) { out.println(-1); } else { out.println(e.answer); } } } } class FastScanner extends BufferedReader { public FastScanner(InputStream is) { super(new InputStreamReader(is)); } public int read() { try { int ret = super.read(); // if (isEOF && ret < 0) { // throw new InputMismatchException(); // } // isEOF = ret == -1; return ret; } catch (IOException e) { throw new InputMismatchException(); } } static boolean isWhiteSpace(int c) { return c >= 0 && c <= 32; } public int nextInt() { int c = read(); while (isWhiteSpace(c)) { c = read(); } int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int ret = 0; while (c >= 0 && !isWhiteSpace(c)) { if (c < '0' || c > '9') { throw new NumberFormatException("digit expected " + (char) c + " found"); } ret = ret * 10 + c - '0'; c = read(); } return ret * sgn; } public String readLine() { try { return super.readLine(); } catch (IOException e) { return null; } } public int[] readIntArray(int n) { int[] ret = new int[n]; for (int i = 0; i < n; i++) { ret[i] = nextInt(); } return ret; } } class FastPrinter extends PrintWriter { public FastPrinter(OutputStream out) { super(out); } } class ArrayUtils { static final long seed = System.nanoTime(); static final Random rand = new Random(seed); static public int[] sortAndUnique(int[] a) { int[] ret = a.clone(); sort(ret); if (ret.length == 0) { return ret; } int last = ret[0]; int j = 1; for (int i = 1; i < ret.length; i++) { if (last != ret[i]) { ret[j++] = ret[i]; last = ret[i]; } } return Arrays.copyOf(ret, j); } public static void sort(int[] a) { shuffle(a); Arrays.sort(a); } public static void shuffle(int[] a) { for (int i = 0; i < a.length; i++) { int j = rand.nextInt(i + 1); int t = a[i]; a[i] = a[j]; a[j] = t; } } } class FenwickMin { int[] min; public FenwickMin(int n) { min = new int[n]; Arrays.fill(min, Integer.MAX_VALUE); } public void setAndMin(int x, int y) { for (int i = x; i < min.length; i |= i + 1) { min[i] = Math.min(min[i], y); } } public int getMin(int x) { x = Math.min(x, min.length - 1); int ret = Integer.MAX_VALUE; for (int i = x; i >= 0; i = (i & i + 1) - 1) { ret = Math.min(ret, min[i]); } return ret; } }