Bizon the Champion has recently finished painting his wood fence. The fence consists of a sequence of n panels of 1 meter width and of arbitrary height. The i-th panel's height is hi meters. The adjacent planks follow without a gap between them.

After Bizon painted the fence he decided to put a "for sale" sign on it. The sign will be drawn on a rectangular piece of paper and placed on the fence so that the sides of the sign are parallel to the fence panels and are also aligned with the edges of some panels. Bizon the Champion introduced the following constraints for the sign position:

  1. The width of the sign should be exactly w meters. 
  2. The sign must fit into the segment of the fence from the l-th to the r-th panels, inclusive (also, it can't exceed the fence's bound in vertical direction). 



The sign will be really pretty, So Bizon the Champion wants the sign's height to be as large as possible.

You are given the description of the fence and several queries for placing sign. For each query print the maximum possible height of the sign that can be placed on the corresponding segment of the fence with the given fixed width of the sign.

Input

The first line of the input contains integer n — the number of panels in the fence (1 ≤ n ≤ 105). 

The second line contains n space-separated integers hi, — the heights of the panels (1 ≤ hi ≤ 109). 

The third line contains an integer m — the number of the queries (1 ≤ m ≤ 105). 

The next m lines contain the descriptions of the queries, each query is represented by three integers l, r and w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ r - l + 1) — the segment of the fence and the width of the sign respectively.

Output

For each query print the answer on a separate line — the maximum height of the sign that can be put in the corresponding segment of the fence with all the conditions being satisfied.

Examples

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5


Output

2
3
1

Note

The fence described in the sample looks as follows: 

<image>

The possible positions for the signs for all queries are given below.

<image> The optimal position of the sign for the first query.  <image> The optimal position of the sign for the second query.  <image> The optimal position of the sign for the third query. 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.function.Supplier;
import java.io.OutputStreamWriter;
import java.util.function.IntFunction;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.function.Consumer;
import java.io.Closeable;
import java.io.Writer;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            ESignOnFence solver = new ESignOnFence();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class ESignOnFence {
        UpdateImpl bufUpd = new UpdateImpl();
        SumImpl bufSum = new SumImpl();
        SegTree<SumImpl, UpdateImpl> st;
        int L;
        int R;
        Query[] qs;
        Machine machine;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            Wall[] walls = new Wall[n];
            for (int i = 0; i < n; i++) {
                walls[i] = new Wall();
                walls[i].x = i;
                walls[i].h = in.ri();
            }
            L = 0;
            R = n - 1;
            st = new SegTree<>(0, n - 1, SumImpl::new, UpdateImpl::new, i -> {
                SumImpl sum = new SumImpl();
                sum.size = 1;
                return sum;
            });
            Arrays.sort(walls, Comparator.comparingInt(x -> x.h));
            UndoOperation[] ops = new UndoOperation[n];
            for (int i = 0; i < n; i++) {
                Wall wall = walls[i];
                ops[i] = new UndoOperation() {

                    public void apply() {
                        bufUpd.mod = 1;
                        st.update(wall.x, wall.x, L, R, bufUpd);
                    }


                    public void undo() {
                        bufUpd.mod = -1;
                        st.update(wall.x, wall.x, L, R, bufUpd);
                    }
                };
            }
            machine = new Machine(n, ops);

            int q = in.ri();
            Query[] qs = new Query[q];
            for (int i = 0; i < q; i++) {
                qs[i] = new Query();
                qs[i].l = in.ri() - 1;
                qs[i].r = in.ri() - 1;
                qs[i].w = in.ri();
            }
            this.qs = qs.clone();
            dac(0, n - 1, 0, q - 1);
            for (Query query : qs) {
                int ans = walls[query.ans].h;
                out.println(ans);
            }
        }

        void dac(int L, int R, int l, int r) {
            assert L <= R;
            if (l > r) {
                return;
            }
            if (L == R) {
                for (int i = l; i <= r; i++) {
                    qs[i].ans = L;
                }
                return;
            }
            int M = (L + R + 1) / 2;
            machine.move(M);
            int m = l;
            for (int i = l; i <= r; i++) {
                bufSum.clear();
                st.query(qs[i].l, qs[i].r, this.L, this.R, bufSum);
                if (bufSum.max < qs[i].w) {
                    SequenceUtils.swap(qs, m, i);
                    m++;
                }
            }
            dac(L, M - 1, l, m - 1);
            dac(M, R, m, r);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class SumImpl implements Sum<SumImpl, UpdateImpl> {
        int left;
        int right;
        int max;
        int size;

        void clear() {
            left = right = max = size = 0;
        }

        public void add(SumImpl sum) {
            max = Math.max(max, sum.max);
            max = Math.max(max, right + sum.left);
            if (left == size) {
                left += sum.left;
            }
            if (sum.right == sum.size) {
                right += sum.right;
            } else {
                right = sum.right;
            }
            size += sum.size;
        }

        public void update(UpdateImpl update) {
            if (update.mod == 1) {
                left = right = max = 1;
            } else {
                left = right = max = 0;
            }
        }

        public void copy(SumImpl sum) {
            max = sum.max;
            size = sum.size;
            left = sum.left;
            right = sum.right;
        }

        public SumImpl clone() {
            SumImpl ans = new SumImpl();
            ans.copy(this);
            return ans;
        }

        public String toString() {
            return "" + max;
        }

    }

    static class UpdateImpl extends CloneSupportObject<UpdateImpl> implements Update<UpdateImpl> {
        int mod;

        public void update(UpdateImpl update) {
            mod = update.mod;
        }

        public void clear() {
            mod = 0;
        }

        public boolean ofBoolean() {
            return mod != 0;
        }

    }

    static class SegTree<S extends Sum<S, U>, U extends Update<U>> implements Cloneable {
        private SegTree<S, U> left;
        private SegTree<S, U> right;
        public S sum;
        private U update;

        private void modify(U x) {
            update.update(x);
            sum.update(x);
        }

        private void pushDown() {
            if (update.ofBoolean()) {
                left.modify(update);
                right.modify(update);
                update.clear();
                assert !update.ofBoolean();
            }
        }

        private void pushUp() {
            sum.copy(left.sum);
            sum.add(right.sum);
        }

        public SegTree(int l, int r, Supplier<S> sSupplier, Supplier<U> uSupplier,
                       IntFunction<S> func) {
            update = uSupplier.get();
            update.clear();
            if (l < r) {
                sum = sSupplier.get();
                int m = DigitUtils.floorAverage(l, r);
                left = new SegTree<>(l, m, sSupplier, uSupplier, func);
                right = new SegTree<>(m + 1, r, sSupplier, uSupplier, func);
                pushUp();
            } else {
                sum = func.apply(l);
            }
        }

        private boolean cover(int L, int R, int l, int r) {
            return L <= l && R >= r;
        }

        private boolean leave(int L, int R, int l, int r) {
            return R < l || L > r;
        }

        public void update(int L, int R, int l, int r, U u) {
            if (leave(L, R, l, r)) {
                return;
            }
            if (cover(L, R, l, r)) {
                modify(u);
                return;
            }
            int m = DigitUtils.floorAverage(l, r);
            pushDown();
            left.update(L, R, l, m, u);
            right.update(L, R, m + 1, r, u);
            pushUp();
        }

        public void query(int L, int R, int l, int r, S s) {
            if (leave(L, R, l, r)) {
                return;
            }
            if (cover(L, R, l, r)) {
                s.add(sum);
                return;
            }
            int m = DigitUtils.floorAverage(l, r);
            pushDown();
            left.query(L, R, l, m, s);
            right.query(L, R, m + 1, r, s);
        }

        public SegTree<S, U> deepClone() {
            SegTree<S, U> clone = clone();
            clone.sum = clone.sum.clone();
            clone.update = clone.update.clone();
            if (clone.left != null) {
                clone.left = clone.left.deepClone();
                clone.right = clone.right.deepClone();
            }
            return clone;
        }

        public void visitLeave(Consumer<SegTree<S, U>> consumer) {
            if (left == null) {
                consumer.accept(this);
                return;
            }
            pushDown();
            left.visitLeave(consumer);
            right.visitLeave(consumer);
        }

        public String toString() {
            StringBuilder ans = new StringBuilder();
            deepClone().visitLeave(x -> ans.append(x.sum).append(' '));
            return ans.toString();
        }

        public SegTree<S, U> clone() {
            try {
                return (SegTree<S, U>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new UnsupportedOperationException(e);
            }
        }

    }

    static class Wall {
        int h;
        int x;

    }

    static abstract class CloneSupportObject<T> implements Cloneable {
        public T clone() {
            try {
                return (T) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static interface Sum<S, U> extends Cloneable {
        void add(S s);

        void update(U u);

        void copy(S s);

        S clone();

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static interface Update<U extends Update<U>> extends Cloneable {
        void update(U u);

        void clear();

        boolean ofBoolean();

        U clone();

    }

    static class Query {
        int l;
        int r;
        int w;
        int ans;

    }

    static interface UndoOperation {
        void apply();

        void undo();

    }

    static class SequenceUtils {
        public static <T> void swap(T[] data, int i, int j) {
            T tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class Machine {
        int cur;
        UndoOperation[] ops;

        public Machine(int cur, UndoOperation[] ops) {
            this.cur = cur;
            this.ops = ops;
        }

        void move(int to) {
            while (cur < to) {
                ops[cur].undo();
                cur++;
            }
            while (cur > to) {
                cur--;
                ops[cur].apply();
            }
        }

    }
}

