CF484E Sign on Fence

冠军 Bizon 最近刚刚涂好了他家的木栅栏。栅栏由 $n$ 块宽为 $1$ 米、高度任意的木板组成，第 $i$ 块木板的高度为 $h_i$ 米。相邻的木板之间没有间隙。 涂完以后，Bizon 决定在栅栏上挂一个“出售”标志。标志由一张长方形纸绘制成，要放在栅栏上，且标志的各边与木板平行，其左右两边正好贴合某些木板的边界。Bizon 给标志的放置提出了如下要求： 1. 标志的宽度必须恰好为 $w$ 米。 2. 标志必须完全放置在从第 $l$ 块到第 $r$ 块（包括）的栅栏区间内（在竖直方向上也不能超出栅栏）。 Bizon 希望标志的高度尽可能大，这样更美观。 你得到了栅栏的描述以及多个关于标志放置的询问。对于每个询问，请输出在给定条件下标志可以放置的最大高度。

输入的第一行包含一个整数 $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$），表示每个询问描述标志要放置的区间及其宽度。

对于每个询问，输出一行答案，表示在满足所有条件的情况下，标志所能放置的最大高度。

样例描述的栅栏如下：  下图给出了所有询问的标志可能放置位置。  第一组询问的最优标志放置位置。  第二组询问的最优标志放置位置。  第三组询问的最优标志放置位置。 由 ChatGPT 5 翻译