Artsem is on vacation and wants to buy souvenirs for his two teammates. There are n souvenir shops along the street. In i-th shop Artsem can buy one souvenir for ai dollars, and he cannot buy more than one souvenir in one shop. He doesn't want to introduce envy in his team, so he wants to buy two souvenirs with least possible difference in price.

Artsem has visited the shopping street m times. For some strange reason on the i-th day only shops with numbers from li to ri were operating (weird? yes it is, but have you ever tried to come up with a reasonable legend for a range query problem?). For each visit, Artsem wants to know the minimum possible difference in prices of two different souvenirs he can buy in the opened shops.

In other words, for each Artsem's visit you should find the minimum possible value of |as - at| where li ≤ s, t ≤ ri, s ≠ t.

Input

The first line contains an integer n (2 ≤ n ≤ 105).

The second line contains n space-separated integers a1, ..., an (0 ≤ ai ≤ 109).

The third line contains the number of queries m (1 ≤ m ≤ 3·105).

Next m lines describe the queries. i-th of these lines contains two space-separated integers li and ri denoting the range of shops working on i-th day (1 ≤ li < ri ≤ n).

Output

Print the answer to each query in a separate line.

Example

Input

8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7


Output

0
1
1
3
/**
 * author: derrick20
 * created: 11/22/20 6:18 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class SouvenirsRedo {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = sc.nextInt();
        TreeSet<Integer> distinct = new TreeSet<>();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
            distinct.add(a[i]);
        }
        TreeMap<Integer, Integer> compress = new TreeMap<>();
        for (int v : distinct) {
            compress.put(v, compress.size());
        }
        int Q = sc.nextInt();
        int[][] queries = new int[Q][3];
        Arrays.setAll(queries, i -> new int[]{i, sc.nextInt() - 1, sc.nextInt() - 1});
        Arrays.sort(queries, Comparator.comparingInt(q -> q[2]));

        int[] ans = new int[Q];
        int oo = (int) 2e9;
        Arrays.fill(ans, oo);
        for (int dir = 0; dir <= 1; dir++) {
            MaxSegTree indexSegTree = new MaxSegTree(N);
            SetSegtree ansSegTree = new SetSegtree(N);
            // dir = 0 => a[i] < a[j]
            // dir = 1 => a[i] > a[j]
            int ptr = 0;
            for (int j = 0; j < N; j++) {
//                System.out.println("Working on " + dir + " " + j);
                int r = compress.get(a[j]);
                int i = dir == 0 ? indexSegTree.query(0, r)
                                 : indexSegTree.query(r, N - 1);
                while (i != -1 && ((dir == 0 && a[i] <= a[j]) || (dir == 1 && a[i] >= a[j]))) {
//                    System.out.println("Next smaller from " + a[j] + " at " + i + " = " + a[i]);
                    ansSegTree.set(0, i, dir == 0 ? a[j] - a[i]
                                                     : a[i] - a[j]);
                    int half = (a[i] + a[j] + (1 - dir)) / 2; // shouldn't affect correctness, just slightly more efficient
                    int mid = dir == 0 ? max(half, a[i] + 1)  // we must be at least a[i] + 1
                                       : min(half, a[i] - 1); // we must be at most  a[i] - 1
//                    if ((dir == 0 && mid >= a[j]) || (dir == 1 && mid <= a[j])) break; // no more vals to get
                    // key bug ^ that's not valid because it's possible we want to reach the value mid = a[j]!
                    Integer next_a = dir == 0 ? compress.ceilingKey(mid)
                                              : compress.floorKey(mid);
                    if (next_a != null) {
                        int l = compress.get(next_a);
                        i = dir == 0 ? indexSegTree.query(l, r) // if i becomes -1, there're no values available
                                     : indexSegTree.query(r, l);
                    } else {
                        break;
                    }
                }
                indexSegTree.update(r, j); // add to our element set
//                for (int k = 0; k < N; k++) {
//                    System.out.print(indexSegTree.query(k, k) + " ");
//                }
//                System.out.println();
//                for (int k = 0; k < N; k++) {
//                    System.out.print(ansSegTree.query(k, k) + " ");
//                }
//                System.out.println();
                while (ptr < Q && queries[ptr][2] == j) {
                    int id = queries[ptr][0];
                    int l = queries[ptr][1];
                    int value = ansSegTree.query(l, j); // we can only use l <= l' <= r' <= j for our answer
                    ans[id] = min(ans[id], value);
                    ptr++;
                }
            }
        }
        for (int i = 0; i < Q; i++) {
            out.println(ans[i]);
        }
        out.close();
    }
/*
4
7 5 6 5
1
1 2

8
7 5 6 5 3 4 2 3
1
1 2
 */
    static class MaxSegTree {
        int[] tree;
        int N;
        int IDENTITY = -1;
        public MaxSegTree(int size) {
            N = size;
            tree = new int[4 * N];
            Arrays.fill(tree, -1);
        }

        void update(int ix, int value) {
            updateHelper(1, 0, N - 1, ix, value);
        }

        void updateHelper(int node, int sl, int sr, int ix, int value) {
            if (ix == sl && sr == ix) {
                tree[node] = max(tree[node], value);
            } else if (sr < ix || ix < sl) {
                return;
            } else {
                int mid = (sl + sr) / 2;
                updateHelper(2 * node, sl, mid, ix, value);
                updateHelper(2 * node + 1, mid + 1, sr, ix, value);
                tree[node] = max(tree[2 * node], tree[2 * node + 1]);
            }
        }

        int query(int l, int r) {
            return queryHelper(1, 0, N - 1, l, r);
        }

        int queryHelper(int node, int sl, int sr, int l, int r) {
            if (l <= sl && sr <= r) {
                return tree[node];
            } else if (sr < l || r < sl) {
                return IDENTITY;
            } else {
                int mid = (sl + sr) / 2;
                return max(
                        queryHelper(2 * node, sl, mid, l, r),
                        queryHelper(2 * node + 1, mid + 1, sr, l, r)
                );
            }
        }
    }

    static class SetSegtree {
        int[] tree, flag;
        int N;
        int IDENTITY = (int) 2e9;
        public SetSegtree(int size) {
            N = size;
            tree = new int[4 * N];
            flag = new int[4 * N];
            Arrays.fill(tree, IDENTITY);
            Arrays.fill(flag, IDENTITY);
        }

        void pushDown(int node) {
            if (flag[node] != IDENTITY) {
                flag[2 * node] = min(flag[2 * node], flag[node]);
                flag[2 * node + 1] = min(flag[2 * node + 1], flag[node]);
                tree[node] = min(tree[node], flag[node]);
                flag[node] = IDENTITY; // now, no pending updates
            }
        }

        int eval(int node) {
            return min(flag[node], tree[node]);
        }

        void pullUp(int node) {
            // invariant: a segment's value will be the minimum of the flag value and the tree value
            // sometimes, it's possible it has a flag that's bad, but is necessary to push down
            // since it may help the children
            int left = eval(2 * node);
            int right = eval(2 * node + 1);
            ASSERT(flag[node] == IDENTITY); // had to have been pushed by this point
            tree[node] = min(left, right);
        }

        void set(int l, int r, int value) {
            setHelper(1, 0, N - 1, l, r, value);
        }

        void setHelper(int node, int sl, int sr, int l, int r, int value) {
            if (l <= sl && sr <= r) {
                if (value < flag[node]) {
                    // only update range if it can make it better
                    flag[node] = value;
                }
            } else if (sr < l || r < sl) {
                return;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                setHelper(2 * node, sl, mid, l, r, value);
                setHelper(2 * node + 1, mid + 1, sr, l, r, value);
                pullUp(node);
            }
        }

        int query(int l, int r) {
            return queryHelper(1, 0, N - 1, l, r);
        }

        int queryHelper(int node, int sl, int sr, int l, int r) {
            if (l <= sl && sr <= r) {
                return eval(node);
            } else if (r < sl || sr < l) {
                return IDENTITY;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                int left = queryHelper(2 * node, sl, mid, l, r);
                int right = queryHelper(2 * node + 1, mid + 1, sr, l, r);
                pullUp(node);
                return min(left, right);
            }
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}