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.io.PrintWriter;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Ronak Vaghela
 */
public class SignOnFence {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskE {
		static public int N;
		static public TreeMap<Integer, Integer> dist;
		static public int[] revMap;
		static public ArrayList<TaskE.Node> nodes;
		static public int[] root;
		static public TaskE.Pair[] p;
		static int cnt;

		public void solve(int testNumber, InputReader in, PrintWriter out) {
			N = in.nextInt();
			p = new TaskE.Pair[N + 1];
			p[0] = new TaskE.Pair(Integer.MIN_VALUE, 0);
			for (int i = 1; i <= N; i++) {
				p[i] = new TaskE.Pair(-in.nextInt(), i);
			}
			int Q = in.nextInt();
			dist = new TreeMap<Integer, Integer>();
			for (int i = 1; i <= N; i++)
				dist.put(p[i].x, 0);

			revMap = new int[dist.size() + 1];
			cnt = 0;
			for (int x : dist.keySet()) {
				dist.put(x, ++cnt);
				revMap[cnt] = x;
			}
			cnt++;

			root = new int[N + 1];
			root[0] = 0;
			nodes = new ArrayList<TaskE.Node>();
			nodes.add(new TaskE.Node());
			Arrays.sort(p);

			int tot = 0;
			for (int i = 1; i <= N; i++) {
				if (p[i].x != p[i - 1].x) {
					tot++;
					root[tot] = update(root[tot - 1], 1, N, p[i].y, 1);
				} else {
					root[tot] = update(root[tot], 1, N, p[i].y, 1);
				}
			}

			// System.out.println(query(1, 1, N, 1, N)[0]);
			// System.out.println(query(2, 1, N, 1, N)[0]);
			// System.out.println(query(3, 1, N, 1, N)[0]);

			StringBuilder sb = new StringBuilder();
			while (Q-- > 0) {
				int u = in.nextInt();
				int v = in.nextInt();
				int x = in.nextInt();
				out.println(solve(u, v, x));
			}

			out.close();
		}

		static int solve(int l, int r, int x) {

			int low = 1;
			int high = cnt - 1;
			int ans = 0;

			while (low <= high) {
				int mid = (low + high) / 2;
				int ee = query(root[mid], l, r, 1, N)[0];
				if (ee >= x) {
					high = mid - 1;
					ans = mid;
				} else {
					low = mid + 1;
				}

			}
			return -revMap[ans];

		}

		static int[] query(int v, int l, int r, int ll, int rr) {
			if (l > r)
				return new int[4];

			if (l == ll && rr == r) {
				int a[] = new int[4];
				a[0] = sum(v);
				a[1] = leftsum(v);
				a[2] = rightsum(v);
				a[3] = num(v);
				return a;
			}

			int xx = (ll + rr) / 2;
			int res[];
			int left[] = new int[4];
			int right[] = new int[4];
			if (l <= xx)
				left = query(left(v), l, Math.min(r, xx), ll, xx);
			if (xx + 1 <= r)
				right = query(right(v), Math.max(xx + 1, l), r, xx + 1, rr);

			return merge(left, right);

		}

		static int[] merge(int[] l, int[] r) {
			// System.out.println(Arrays.toString(l));
			// System.out.println(Arrays.toString(r));
			// System.out.println(lEnd + a[lEnd] + " " + a[rStart]);
			int ret[] = new int[4];
			ret[0] = Math.max(l[0], r[0]);
			ret[1] = l[1];
			ret[2] = r[2];
			ret[3] = 0;
			ret[0] = Math.max(ret[0], l[2] + r[1]);
			ret[3] = Math.min(l[3], r[3]);
			if (l[3] == 1)
				ret[1] = l[1] + r[1];
			if (r[3] == 1)
				ret[2] = l[2] + r[2];

			return ret;
		}

		static int update(int prevRoot, int start, int end, int x, int add) {
			TaskE.Node now = new TaskE.Node();
			now.sum = sum(prevRoot);
			now.left = left(prevRoot);
			now.right = right(prevRoot);
			now.rightsum = rightsum(prevRoot);
			now.leftsum = leftsum(prevRoot);
			now.num = num(prevRoot);

			nodes.add(now);
			int idx = nodes.size() - 1;
			if (start == end) {
				now.sum += add;
				now.rightsum += add;
				now.leftsum += add;
				now.num = 1;
				return idx;
			}
			int mid = (start + end) >> 1;
			if (x <= mid) {
				int leftSon = left(prevRoot);
				now.left = update(leftSon, start, mid, x, add);
			} else {
				int rightSon = right(prevRoot);
				now.right = update(rightSon, mid + 1, end, x, add);
			}

			now.sum = Math.max(sum(now.left), sum(now.right));
			now.sum = Math.max(now.sum,
					rightsum(now.left) + leftsum(now.right));

			now.leftsum = leftsum(now.left);
			now.rightsum = rightsum(now.right);

			if (num(now.left) == 1) {
				now.leftsum = leftsum(now.left) + leftsum(now.right);
			}
			if (num(now.right) == 1) {
				now.rightsum = rightsum(now.left) + rightsum(now.right);
			}
			now.num = Math.min(num(now.left), num(now.right));
			return idx;
		}

		static int sum(int idx) {
			return idx == -1 ? 0 : nodes.get(idx).sum;
		}

		static int leftsum(int idx) {
			return idx == -1 ? 0 : nodes.get(idx).leftsum;
		}

		static int rightsum(int idx) {
			return idx == -1 ? 0 : nodes.get(idx).rightsum;
		}

		static int num(int idx) {
			return idx == -1 ? 0 : nodes.get(idx).num;
		}

		static int left(int idx) {
			return idx == -1 ? -1 : nodes.get(idx).left;
		}

		static int right(int idx) {
			return idx == -1 ? -1 : nodes.get(idx).right;
		}

		static class Node {
			int sum;
			int leftsum;
			int rightsum;
			int num;
			int left;
			int right;

			Node() {
				sum = 0;
				left = -1;
				right = -1;
				num = 0;
				leftsum = 0;
				rightsum = 0;
				sum = 0;
			}

		}

		static public class Pair implements Comparable<TaskE.Pair> {
			int x;
			int y;

			public Pair(int x, int y) {
				this.x = x;
				this.y = y;
			}

			public int compareTo(TaskE.Pair o) {
				if (x != o.x)
					return Integer.compare(x, o.x);
				return Integer.compare(y, o.y);
			}

		}

	}

	static class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar;
		private int snumChars;
		private InputReader.SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);

		}

	}
}
