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.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		if (new File("input.txt").exists())
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		if (new File("output.txt").exists())
			out = new PrintWriter("output.txt");
		else
			out = new PrintWriter(System.out);

		solve();

		in.close();
		out.close();
	}

	final int maxn = 100 * 1000 + 100;

	int n;

	Value values[] = new Value[maxn];
	SeqmentTree trees[] = new SeqmentTree[maxn];

	SeqmentTree tree;

	void solve() throws IOException {
		n = nextInt();
		for (int i = 0; i < n; i++)
			values[i] = new Value(nextInt(), i);

		sort(values, 0, n);

		tree = new SeqmentTree(n);
		for (int i = 0; i < n; i++) {
			tree.setOne(values[i].index);
			trees[i] = tree.cloneTree();
		}

		int countRequest = nextInt();
		for (int request = 0; request < countRequest; request++) {
			final int ll = nextInt() - 1;
			final int rr = nextInt() - 1;
			final int w = nextInt();

			int l = -1;
			int r = n - 1;
			while (r - l > 1) {
				int m = (l + r) / 2;

				if (trees[m].getCountOne(ll, rr) >= w)
					r = m;
				else
					l = m;
			}

			out.println(values[r].a);
		}

	}

	class Value implements Comparable<Value> {
		int a;
		int index;

		public Value(int a, int index) {
			super();
			this.a = a;
			this.index = index;
		}

		@Override
		public int compareTo(Value o) {
			return Integer.compare(o.a, a);
		}

	}

	class SeqmentTree {

		int n;
		Node root;

		public SeqmentTree(int size) {
			n = 1;
			while (n < size)
				n <<= 1;

			root = new Node(0, n - 1);
			build(root, 0, n - 1);
		}

		public SeqmentTree(Node root) {
			this.root = root;
			n = root.len;
		}

		public SeqmentTree cloneTree() {
			return new SeqmentTree(root);
		}

		void build(Node node, int l, int r) {
			if (l == r)
				return;

			int m = (l + r) >> 1;
			Node left = new Node(l, m);
			Node right = new Node(m + 1, r);
			node.left = left;
			node.right = right;
			build(left, l, m);
			build(right, m + 1, r);
		}

		void setOne(int index) {
			root = setOne(root, index);
		}

		int getCountOne(int l, int r) {
			return getCountOne(root, l, r);
		}

		int getCountOne(Node node, int l, int r) {
			if (r < l)
				return -1;

			if (node.l == l && node.r == r)
				return node.maxLength;

			int m = (node.l + node.r) >> 1;

			if (r <= m)
				return getCountOne(node.left, l, r);
			else if (l > m)
				return getCountOne(node.right, l, r);
			else {
				int countl = getCountOne(node.left, l, m);
				int countr = getCountOne(node.right, m + 1, r);
				int count = min(node.left.maxSuffix, m - l + 1) + min(node.right.maxPrefix, r - m);
				return max(max(countl, countr), count);
			}
		}

		Node setOne(Node node, int index) {
			final int l = node.l;
			final int r = node.r;
			if (l == r) {
				Node newNode = new Node(l, r);
				newNode.value = 1;
				newNode.update();
				return newNode;
			}

			final int m = (l + r) >> 1;
			if (index <= m) {
				Node left = setOne(node.left, index);
				Node newNode = new Node(l, r);
				newNode.left = left;
				newNode.right = node.right;
				newNode.update();
				return newNode;
			} else {
				Node right = setOne(node.right, index);
				Node newNode = new Node(l, r);
				newNode.left = node.left;
				newNode.right = right;
				newNode.update();
				return newNode;
			}
		}

		class Node {
			Node left;
			Node right;
			final int l, r;
			final int len;

			int value;
			int maxLength;
			int maxPrefix;
			int maxSuffix;

			public Node(int l, int r) {
				this.l = l;
				this.r = r;
				len = r - l + 1;
				value = 0;
				maxLength = 0;
				maxPrefix = 0;
				maxSuffix = 0;
				left = right = null;
			}

			void update() {
				if (l == r) {
					maxLength = value;
					maxPrefix = value;
					maxSuffix = value;
				} else {
					maxLength = max(left.maxLength, right.maxLength);
					maxLength = max(maxLength, left.maxSuffix + right.maxPrefix);

					maxPrefix = left.maxPrefix;
					if (maxPrefix == left.len)
						maxPrefix += right.maxPrefix;

					maxSuffix = right.maxSuffix;
					if (maxSuffix == right.len)
						maxSuffix += left.maxSuffix;
				}
			}

		}
	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String str = in.readLine();
			if (str == null)
				return true;
			st = new StringTokenizer(str);
		}
		return false;
	}

}
