1007. rains

题目描述

下雨了。

一共有 $n$ 块石头，第 $i$ 块石头高度为 $h_i$，这些石头初始是连接在一起的。

如果下雨，当雨水高度大于 $h_i$ 的时候，这块石头就会被淹没。

因此，在下雨的时候，露出水面的石头们会变成多个连续段。

小 H 每次询问：拿出区间 $[l, r]$ 的石头，至少形成 $k$ 个连续段的情况下，最高的雨水高度是多少。

输入格式

第一行三个整数 $n, T, k（1\le n,T,k\le 10^6）$，表示石头个数和询问次数以及要求的连续段数量。

接下来一行输入 $n$ 个正整数，每个表示石头高度 $h_i（1\le h_i\le 10^6）$。

接下来 $T$ 行，每行两个正整数 $l, r（1\le l\le r\le n）$，表示一次询问。

输出格式

每个询问输出一个整数表示答案，如果这组询问无解，输出 -1。

样例输入

10 10 3
8 10 7 9 5 2 6 1 4 5
3 4
6 6
3 4
1 9
1 8
2 9
5 7
5 10
4 7
6 10

样例输出

-1
-1
-1
4
-1
4
-1
5
-1
-1

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1007