시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB933330.000%

문제

You are given a sequence $a_1,\dots , a_n$ and $q$ independent queries. In each query you are given two integers $l$ and $r$. Consider the sequence $a_l , a_{l+1}, \dots , a_r$. Your task is to compute the sum of the minimum excluded element of all sequences of form $a_i , a_{i+1}, \dots , a_j$, for $l ≤ i ≤ j ≤ r$.

The minimum excluded element of a sequence is the smallest non-negative integer that does not appear in the sequence. For example, for the sequence $0$, $1$, $4$, $2$ it is $3$, but the for the sequence $1$, $2$, $3$, $4$ it is $0$.

입력

The first line of the input contains the integers $n$ and $q$. The second line contains $n$ integers $a_1, a_2, \dots , a_n$, representing the initial sequence. Each of the next $q$ lines contains two integers $l$ and $r$, describing each query.

출력

The output should contain the answers to the $q$ queries in order, each on a new line.

제한

  • $1 ≤ n, q ≤ 2 · 10^5$
  • $0 ≤ a_i ≤ n$
  • $1 ≤ l ≤ r ≤ n$

서브태스크

번호배점제한
13

$1 ≤ a_i ≤ n$

210

$1 ≤ q ≤ 200$; $r - l ≤ 200$

312

$1 ≤ n ≤ 5000$

415

Each number from $0$ to $n - 1$ appears exactly once in $a_1, a_2, \dots , a_n$.

515

$0 ≤ a_i ≤ 100$ and there are no two queries $i$ and $j$ such that $l_i < l_j$ and $r_j < r_i$.

622

$l = 1$ for each query.

723

No further restrictions.

예제 입력 1

6 3
0 1 2 0 1 3
1 2
3 5
1 6

예제 출력 1

3
7
39

힌트

Explanation for the first queries:

Subsequence Min. excl. elem.
$0$ $1$
$1$ $0$
$0$, $1$ $2$
Total: $3$

Explanation for the second queries:

Subsequence Min. excl. elem.
$2$ $0$
$0$ $1$
$1$ $0$
$2$, $0$ $1$
$0$, $1$ $2$
$2$, $0$, $1$ $3$
Total: $7$

Explanation for the third query:

Subsequence Min. excl. elem.
$0$ $1$
$0$, $1$ $2$
$0$, $1$, $2$ $3$
$0$, $1$, $2$, $0$ $3$
$0$, $1$, $2$, $0$, $1$ $3$
$0$, $1$, $2$, $0$, $1$, $3$ $4$
$1$ $0$
$1$, $2$ $0$
$1$, $2$, $0$ $3$
$1$, $2$, $0$, $1$ $3$
$1$, $2$, $0$, $1$, $3$ $4$
$2$ $0$
$2$, $0$ $1$
$2$, $0$, $1$ $3$
$2$, $0$, $1$, $3$ $4$
$0$ $1$
$0$, $1$ $2$
$0$, $1$, $3$ $2$
$1$ $0$
$1$, $3$ $0$
$3$ $0$
Total: $39$

채점 및 기타 정보

  • 예제는 채점하지 않는다.