冠军 Bizon 最近完成了他的木栅栏的油漆。栅栏由一系列 n 个 1 米宽、任意高度的面板组成。第 i 个面板的高度为 hi 米。相邻的木板紧随其后,之间没有间隙。
Bizon 粉刷了栅栏后,他决定在上面贴上“出售”标志。该标牌将绘制在一张矩形纸上并放置在栅栏上,使标牌的侧面与栅栏板平行,并与某些板的边缘对齐。 Bizon the Champion 对标志位置引入了以下限制:
1. 标志的宽度应恰好为 w 米。
2. 标志必须适合栅栏从第 l 块到第 r 块(含)的部分(而且,它不能超出栅栏在垂直方向的边界)。
标牌会非常漂亮,所以冠军 Bizon 希望标牌的高度尽可能大。
您将获得围栏的描述以及放置标志的几个查询。对于每个查询,打印可以放置在具有给定固定宽度的围栏相应段上的标志的最大可能高度。
输入
输入的第一行包含整数 n — 围栏中的面板数量 (1 ≤ n ≤ 105)。
第二行包含 n 个空格分隔的整数 hi,— 面板的高度 (1 ≤ hi ≤ 109)。
第三行包含一个整数 m — 查询的数量 (1 ≤ m ≤ 105)。
接下来的 m 行包含查询的描述,每个查询由三个整数 l、r 和 w 表示(1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ r - l + 1)——分别是围栏的段和标志的宽度。
输出
对于每个查询,将答案打印在单独的行上 - 在满足所有条件的情况下,可以放置在栅栏相应部分中的标志的最大高度。
示例
输入 #1
5 1 2 2 3 3 3 2 5 3 2 5 2 1 5 5
输出 #1
2 3 1
注意
示例中描述的围栏如下所示:
下面给出了所有查询的符号的可能位置。
第一个查询的标志的最佳位置。
第二次查询的标志的最佳位置。
第三次查询的标志的最佳位置。