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.util.*;
import java.io.*;
import java.text.*;

public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC) throws Exception {
        int n = ni();
        int[] h = new int[1+n];
        int[][] p = new int[1+n][];
        for(int i = 1; i<= n; i++){
            h[i] = ni();
            p[i] = new int[]{i, h[i]};
        }
        Arrays.sort(p, 1, n+1, (int[] i1, int[] i2) -> Integer.compare(i2[1], i1[1]));

        Node[] root = new Node[1+n];
        root[0] = build(1, n);
        for(int i = 1; i<= n; i++){
            int pos = p[i][0];
            root[i] = update(root[i-1], pos, 1, n);
        }
        for(int m = ni(); m>0; m--){
            int L = ni(), R = ni(), W = ni();
            int lo = 0, hi = n;
            while(lo+1 < hi){
                int mid = lo+(hi-lo)/2;
                if(query(root[mid], L, R, 1, n) >= W)hi = mid;
                else lo = mid;
            }
            if(query(root[lo], L, R, 1, n) >= W)hi = lo;
            pn(p[hi][1]);
        }
    }
    int query(Node root, int l, int r, int ll, int rr){
        return q(root, l, r, ll, rr).max;
    }
    Node q(Node root, int l, int r, int ll, int rr){
        if(l == ll && r == rr)return root;
        int mid = (ll+rr)/2;
        if(r <= mid)return q(root.le, l, r, ll, mid);
        else if(l > mid)return q(root.ri, l, r, mid+1, rr);
        else return merge(q(root.le, l, mid, ll, mid), q(root.ri, mid+1, r, mid+1, rr));
    }
    Node update(Node root, int pos, int ll, int rr) throws Exception{
        if(ll == rr)
            return new Node(1);
        hold(root != null);
        Node le = root.le, ri = root.ri;
        int mid = (ll+rr)/2;
        if(pos <= mid)le = update(le, pos, ll, mid);
        else ri = update(ri, pos, mid+1, rr);
        return merge(le, ri);
    }
    Node build(int ll, int rr){
        if(ll == rr)return new Node(0);
        int mid = (ll+rr)/2;
        return merge(build(ll, mid), build(mid+1, rr));
    }
    void print(Node root, int ll, int rr){
        if(ll == rr)p(root.max+" ");
        else{
            int mid = (ll+rr)/2;
            print(root.le, ll, mid);
            print(root.ri, mid+1, rr);
        }
    }
    class Node{
        Node le, ri;
        int max, pre, suf, len;
        public Node(int val){
            le = null;
            ri = null;
            max = pre = suf = val;
            len = 1;
        }
        public Node(Node x){
            le = x.le;
            ri = x.ri;
            max = x.max;
            pre = x.pre;
            suf = x.suf;
            len = x.len;
        }
        public Node(int max, int pre, int suf, int len, Node le, Node ri){
            this.max = max;
            this.pre = pre;
            this.suf = suf;
            this.len = len;
            this.le = le;
            this.ri = ri;
        }
    }
    Node merge(Node le, Node ri){
        if(le == null)return new Node(ri);
        if(ri == null)return new Node(le);

        int max = Math.max(Math.max(le.max, ri.max), le.suf+ri.pre);
        int pre = (le.pre == le.len)?(le.len+ri.pre):le.pre;
        int suf = (ri.suf == ri.len)?(ri.len+le.suf):ri.suf;
        int len = le.len+ri.len;
        return new Node(max, pre, suf, len, le, ri);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    final long IINF = (long)2e18;
    final int INF = (int)1e9+2, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        long ct = System.currentTimeMillis();
        if (fileIO) {
            in = new FastReader("");
            out = new PrintWriter("");
        } else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = multipleTC? ni():1;
        pre();
        for (int t = 1; t <= T; t++) solve(t);
        out.flush();
        out.close();
        System.err.println(System.currentTimeMillis() - ct);
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int[][] make(int n, int[] from, int[] to, int e, boolean f){
        int[][] g = new int[n][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            if(f)g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int[][][] makeS(int n, int[] from, int[] to, boolean f){
        int[][][] g = new int[n][][];int[]cnt = new int[n];
        for(int i:from)cnt[i]++;if(f)for(int i:to)cnt[i]++;
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]][];
        for(int i = 0; i< from.length; i++){
            g[from[i]][--cnt[from[i]]] = new int[]{to[i], i};
            if(f)g[to[i]][--cnt[to[i]]] = new int[]{from[i], i};
        }
        return g;
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str;
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}