#152 seqquery1

Loading problem...

Preparing the statement, recent submissions, and submit form.

#152 seqquery1 | DOJ

Authors: lunarlity

Time limit: 4000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

KO EN

길이 $N$ 의 정수 수열 $A_1, A_2, \cdots, A_N$ 이 주어진다.

당신은 $Q$ 개의 쿼리를 처리해야 한다. 각 쿼리는 두 정수 $l, r$ 로 주어진다.

쿼리마다 정수 $k$ 를 $l \le k\le r$ 가 되도록 하나 고른다. 그 후 길이 $k-l+1$ 의 정수 수열 $B_l, B_{l+1}, \cdots, B_k$ 를 고른다. $B$ 는 다음 조건을 만족해야 한다.

$B_l \le B_{l+1} \le \cdots \le B_k$

모든 $l\le i\le k$ 에 대해 $B_i\le A_i$ 이다.

이때 $B_l + B_{l+1} + \cdots + B_k$ 의 최댓값을 출력하여라.

Input

첫째 줄에 두 정수 $N, Q$ 가 공백으로 구분되어 주어진다

둘째 줄에 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다.

다음 $Q$ 개의 줄에는 쿼리를 나타내는 두 정수 $l, r$ 가 공백으로 구분되어 주어진다.

Output

각 쿼리마다 정답을 한 줄에 하나씩 출력한다.

Constraints

$1 \le N, Q \le 150\ 000$
$-10^9 \le A_i \le 10^9$
$1 \le l\le r \le N$
입력으로 주어지는 모든 수는 정수이다.

Subtasks

#	Score	Constraints
1	5	$N, Q \le 35$
2	10	$N, Q \le 450$
3	10	$N, Q \le 150\ 000$ 이고 모든 쿼리의 길이는 $450$ 이하이다.
4	15	$N \le 5\ 000, Q\le 150\ 000$
5	10	$N, Q \le 150\ 000$ 이고 A는 비감소 또는 비증가 수열이다.
6	15	$N, Q \le 150\ 000$ 이고 모든 $i$ 에 대해 $A_i\ge 1$ 이다.
7	35	추가 제한이 없다.

Samples

Sample 1

Input

Output

Sample 2

Input

Output

95
100
-1

수열과 쿼리 1

Statement

Input

Output

Constraints

Subtasks

Samples