3861: Keen On Everything But Triangle
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：8
解决：2
题目描述
N sticks are arranged in a row, and their lengths are a1,a2,...,aN.
There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.
There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.
输入
There are multiple test cases.
Each case starts with a line containing two positive integers N,Q(N,Q≤1e5).
The second line contains N integers, the i-th integer ai(1≤ai≤1e9) of them showing the length of the i-th stick.
Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×1e5.
Each case starts with a line containing two positive integers N,Q(N,Q≤1e5).
The second line contains N integers, the i-th integer ai(1≤ai≤1e9) of them showing the length of the i-th stick.
Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×1e5.
输出
For each test case, output Q lines, each containing an integer denoting the maximum circumference.
样例输入 复制
5 3
2 5 6 5 2
1 3
2 4
2 5样例输出 复制
13
16
16