F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Keen On Everything But Triangle

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 6362    Accepted Submission(s): 1565


Problem Description
$N$ sticks are arranged in a row, and their lengths are $a_1, a_2, ... , a_N$.

There are $Q$ querys. For $i$-th of them, you can only use sticks between $l_i$-th to $r_i$-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.
 

Input
There are multiple test cases.

Each case starts with a line containing two positive integers $N,Q(N, Q \leq 10^5)$.

The second line contains $N$ integers, the $i$-th integer $a_i(1 \leq a_i \leq 10^9)$ of them showing the length of the $i$-th stick.

Then follow $Q$ lines. $i$-th of them contains two integers $l_i, r_i(1 \leq l_i \leq r_i \leq N)$, meaning that you can only use sticks between $l_i$-th to $r_i$-th.

It is guaranteed that the sum of $N$s and the sum of $Q$s in all test cases are both no larger than $4 \times 10^5$.
 

Output
For each test case, output $Q$ lines, each containing an integer denoting the maximum circumference.
 

Sample Input
5 3 2 5 6 5 2 1 3 2 4 2 5
 

Sample Output
13 16 16
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 18:17:27, Gzip enabled