CF484E.Sign on Fence

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 h__i 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.

冠军比松最近刚刚粉刷完他的木栅栏。该栅栏由一排 $n$ 块宽度为 1 米、高度任意的木板组成。第 $i$ 块木板的高度为 $h_i$ 米。相邻木板之间紧密拼接，无空隙。

比松粉刷完栅栏后，决定在上面贴一张“出售”告示。该告示将绘制在一张矩形纸上，并贴在栅栏上，使得告示的边与栅栏木板平行，且其左右边界恰好与某些木板的边缘对齐。冠军比松对告示的位置提出了如下约束：

1. 告示的宽度必须恰好为 $w$ 米；
2. 告示必须完全位于栅栏的第 $l$ 块至第 $r$ 块木板（含端点）所构成的区间内（同时，在竖直方向上也不能超出栅栏边界）。

这张告示将非常美观，因此冠军比松希望告示的高度尽可能大。

你将获得栅栏的描述以及若干条关于张贴告示的查询。对每条查询，请输出在给定固定宽度 $w$ 的前提下，能在对应栅栏区间 $[l, r]$ 上放置的告示的最大可能高度。

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 h__i, — the heights of the panels (1 ≤ h__i ≤ 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.

输入的第一行包含一个整数 $n$ —— 围栏中木板的数量（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个用空格分隔的整数 $h_i$ —— 各木板的高度（$1 \leq h_i \leq 10^9$）。

第三行包含一个整数 $m$ —— 查询的数量（$1 \leq m \leq 10^5$）。

接下来的 $m$ 行描述了各次查询，每次查询由三个整数 $l$、$r$ 和 $w$ 表示（$1 \leq l \leq r \leq n$，$1 \leq w \leq r - l + 1$），分别表示围栏的区间和标识牌的宽度。

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.

对于每个查询，在单独的一行中输出答案——即在满足所有条件的前提下，可放置在对应围栏区段中的告示牌的最大高度。

The fence described in the sample looks as follows:

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

The optimal position of the sign for the first query.

The optimal position of the sign for the second query.

The optimal position of the sign for the third query.

样例中描述的栅栏如下所示：

所有查询中指示牌可能放置的位置如下所示。

第一个查询的指示牌最优位置。

第二个查询的指示牌最优位置。

第三个查询的指示牌最优位置。