#438 MEX Interval Score

Statement

Statement language

You are given a length- $N$ sequence $A$ of nonnegative integers, a length- $(N+1)$ sequence $B$ , and a length- $N$ sequence $C$ . The indices of $B$ range from $0$ to $N$ , while the other sequences are indexed from $1$ to $N$ .

For a nonempty sequence $X$ , $\operatorname{mex}(X)$ is the smallest nonnegative integer that does not occur in $X$ .

The score of an interval $[s,e]$ is defined as

B_{\operatorname{mex}(A_s,A_{s+1},\cdots,A_e)}-\sum_{i=s}^{e}C_i.

You are given $Q$ queries. For each query $[l,r]$ , find the maximum score among all intervals $[s,e]$ satisfying $l\le s\le e\le r$ .

Input

The input is given from Standard Input in the following format:

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$

Output

For each query, print the maximum score of a valid interval on its own line.

Constraints

$1\le N,Q\le 300\,000$ .
$0\le A_i\le N$ ().

Subtasks

#	Score	Constraints
1	15	$N\le 50$ . $Q\le 50$ .
2	26	$N\le 2\,000$ .

Samples

Input

4
2 1 0
10 20 30 40
2 3 4
4
3
1
4

Output

For the first query, interval $[1,3]$ has MEX $3$ and score $30-(1+2+3)=24$ .