#451 LIS and query 2

Loading problem...

Preparing the statement, recent submissions, and submit form.

#451 LIS and query 2 | DOJ

Authors: dyppp

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

Statement

A subsequence of a sequence $B$ of length $N$ is a sequence obtained by removing zero or more elements from $B$ . The order of the remaining elements must be the same as in $B$ .

A subsequence is nondecreasing if every element is greater than or equal to the preceding element. Let $f(B)$ be the length of a longest nondecreasing subsequence of $B$ .

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ . For $1 \leq x \leq y \leq N$ , define

A[x:y]=[A_x,A_{x+1},\cdots,A_y].

You are also given $Q$ queries. For each query $(l,r)$ , compute

\sum_{x=l}^{r}\sum_{y=x}^{r} f(A[x:y]).

Input

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

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_Q\ r_Q$

Output

For each test case, print $Q$ lines. The $j$ -th line must contain the answer to the $j$ -th query.

Constraints

$1 \leq T \leq 20$ .
$1 \leq N \leq 1\,000\,000$ .
$1 \leq Q \leq 1\,000\,000$ .
$1 \leq A_i \leq 3$ ( $1 \leq i \leq N$ ).
$1 \leq l_j \leq r_j \leq N$ ( $1 \leq j \leq Q$ ).
The sum of $N$ over all test cases does not exceed $1\,000\,000$ .
The sum of $Q$ over all test cases does not exceed $1\,000\,000$ .
All values in the input are integers.

Subtasks

#	Score	Constraints
1	11	$N,Q \leq 200$ in each test case. The sum of $N$ over all test cases does not exceed $200$ . The sum of $Q$ over all test cases does not exceed $200$ .
2	24	$A_i \leq 2$ ( $1 \leq i \leq N$ ).
3	25	$N,Q \leq 200\,000$ in each test case. The sum of $N$ over all test cases does not exceed $200\,000$ . The sum of $Q$ over all test cases does not exceed $200\,000$ .
4	40	No additional constraints.

Samples

Input

Output

The first query of the first test case contains six contiguous subarrays. Their values of $f$ are $1,1,2,1,2,1$ , whose sum is $8$ .

The sequence in the second test case is nondecreasing. For its first query, the sum of the lengths of all contiguous subarrays is $20$ .