问题2476--达瓦的序列2476: 达瓦的序列
时间限制: 1 Sec 内存限制: 256 MB
提交: 1 解决: 1
[提交] [状态] [讨论版] [命题人:]题目描述
达瓦吃着麻辣鸭脖，喝着牛奶觉得美滋滋，然后他拿出一个序列研究了起来。达瓦定义一个序列的al, al+1, ……, ar的价值为(r - l + 1)Σai(i=l, l+1, ……, r)。
现在他手里有一个长度为n的序列a1, a2, ……, an，他想知道在区间[l, r]中所有满足价值不小于x的连续子序列的最大元素的最小值是多少。
达瓦很想知道答案，但是他无暇他顾（还在吃鸭脖），所以他想请你帮忙计算。
输入
有多组数据，第一行一个整数T，表示数据组数。
对于每组输入数据，第一行一个正整数n(1 ⩽ n ⩽ 50000)，表示给定序列的长度。
接下来一行n个正整数，表示a1, a2, ……, an，1 ⩽ ai ⩽ 107。
接下来一行一个正整数q(1 ⩽ q ⩽ 50000)，表示询问次数。
接下来q行，每个三个正整数li，ri，xi，(1 ⩽ li ⩽ ri ⩽ n, 1 ⩽ xi ⩽ 1018)，含义如题面所示。
保证在所有数据中Σn ⩽ 100000，Σq ⩽ 100000。
输出
对于每个询问输出一行一个整数。若存在满足条件的连续子序列，输出所有满足条件的子序列的最大元素中的最小值，否则输出-1。
样例输入
2
5
1 1 2 3 4
2
1 5 10
1 2 5
5
1 3 2 4 6
4
1 3 3
1 3 2
2 4 10
1 1 900
样例输出
2
-1
3
2
3
-1
提示
关于样例1的解释：
第一个询问，在区间[1, 5]中满足价值不小于10的连续子序列有[1, 1, 2]，[1, 1, 2, 3]，[1, 1, 2, 3, 4]，[1, 2, 3]，[1, 2, 3, 4]，[2, 3]，[2, 3, 4]，[3, 4]，这些序列的最大元素分别为2，3，4，3，4，3，4，4，所以答案为2。
第二个询问，在区间[1, 2]中不存在满足价值不小于5的连续子序列，所以答案为-1。
来源/分类
[提交] [状态]