Sign on Fence

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

栅栏由 $n$ 块宽度均为 $1$、高度为 $h_i$ 的连续木板组成，相邻木板之间没有间隙。现在要在栅栏上放置一个矩形标志，标志的各边与木板平行，左右两边正好贴合某些木板的边界。

每次询问给出 $l,r,w$。标志宽度必须恰为 $w$，并且必须完全位于第 $l$ 至第 $r$ 块木板所构成的栅栏区间内。求标志可能达到的最大高度。

输入格式

第一行一个整数 $n$，表示木板数量。

第二行 $n$ 个整数 $h_i$，表示每块木板的高度。

第三行一个整数 $m$，表示询问数量。随后 $m$ 行每行三个整数 $l,r,w$。

输出格式

每个询问输出一行最大高度。

样例输入 1

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

样例输出 1

2
3
1

数据范围

对于全部数据，$1\le n,m\le10^5$，$1\le h_i\le10^9$，$1\le l\le r\le n$，$1\le w\le r-l+1$。

所有测试点均独立计分且分值相同。

提示

样例描述的栅栏如下：

下图分别给出了三次询问的一种最优放置方式：