310646: CF1864F. Exotic Queries

F. Exotic Queriestime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

AquaMoon gives RiverHamster a sequence of integers $a_1,a_2,\dots,a_n$, and RiverHamster gives you $q$ queries. Each query is expressed by two integers $l$ and $r$.

For each query independently, you can take any continuous segment of the sequence and subtract an identical non-negative value from all the numbers of this segment. You can do so multiple (possibly, zero) times. However, you may not choose two intersecting segments which are not included in one another. Your goal is to convert to $0$ all numbers whose initial value was within the range $[l, r]$. You must do so in the minimum number of operations.

Please note that the queries are independent, the numbers in the array are restored to their initial values between the queries.

Formally, for each query, you are to find the smallest $m$ such that there exists a sequence $\{(x_j,y_j,z_j)\}_{j=1}^{m}$ satisfying the following conditions:

• for any $1 \le j \leq m$, $z_j \ge 0$ and $1 \le x_j \le y_j \leq n$ (here $[x_j, y_j]$ correspond to the segment of the sequence);
• for any $1 \le j < k \le m$, it is true that $[x_j,y_j]\subseteq[x_{k},y_{k}]$, or $[x_k,y_k]\subseteq[x_{j},y_{j}]$, or $[x_j,y_j]\cap[x_{k},y_{k}]=\varnothing$;
• for any $1 \le i \le n$, such that $l \le a_i \leq r$, it is true that $${\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j. }$$

Input

The first line contains two integers $n$ and $q$ ($1\le n,q\le 10^6$).

The second line contains $n$ integers integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

Each of the next $q$ lines contains two integers $l$ and $r$ ($1\le l\le r\le n$), representing a query.

Output

For each query, output the answer for this query on a separate line.

ExamplesInput

10 8
1 6 2 3 2 6 3 10 1 2
1 10
2 2
3 3
2 3
1 3
3 6
4 6
5 5

Output

8
1
1
3
5
3
1
0

Input

3 1
1 3 2
1 3

Output

3

Note

In the first test case, consider the second query, when $l = 2$, $r = 2$. The elements to be manipulated are $[a_3, a_5, a_{10}] = [2, 2, 2]$. It is sufficient to apply the operation sequence $\{(2, 10, 2)\}$.

Consider the fourth query, when $l = 2$, $r = 3$. The elements to be manipulated are $[a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]$. It is sufficient to apply the operation sequence $\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}$.

In the second test case, note that the operation sequence $\{(1, 2, 1), (2, 3, 2)\}$ is invalid because the two segments intersect but neither is contained inside the other.

题目大意：
题目名为“异国情调的查询”(Exotic Queries)。给定一个整数序列 $a_1, a_2, \dots, a_n$，以及 $q$ 个查询，每个查询由两个整数 $l$ 和 $r$ 表示。对于每个查询，你可以选择序列中的任意连续段，并从该段中的所有数字减去相同的非负值。你可以执行多次（可能为零次）这样的操作，但不得选择两个相交且不包含彼此的段。目标是将初始值在 $[l, r]$ 范围内的所有数字转换为 $0$，并且要使用最少的操作次数。请注意，查询是独立的，数组中的数字在查询之间会恢复到它们的初始值。

输入数据格式：
第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^6$)。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)。
接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，代表一个查询。

输出数据格式：
对于每个查询，输出一行表示该查询的答案。

公式（使用 LaTeX 格式）：
对于每个查询，你需要找到最小的 $m$，使得存在一个序列 $\{(x_j,y_j,z_j)\}_{j=1}^{m}$ 满足以下条件：
1. 对于任意 $1 \le j \le m$，有 $z_j \ge 0$ 和 $1 \le x_j \le y_j \le n$（这里 $[x_j, y_j]$ 对应于序列的段）；
2. 对于任意 $1 \le j < k \le m$，满足 $[x_j,y_j] \subseteq [x_k,y_k]$，或 $[x_k,y_k] \subseteq [x_j,y_j]$，或 $[x_j,y_j] \cap [x_k,y_k] = \varnothing$；
3. 对于任意 $1 \le i \le n$，如果 $l \le a_i \le r$，则满足 $a_i = \sum_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j$。题目大意： 题目名为“异国情调的查询”(Exotic Queries)。给定一个整数序列 $a_1, a_2, \dots, a_n$，以及 $q$ 个查询，每个查询由两个整数 $l$ 和 $r$ 表示。对于每个查询，你可以选择序列中的任意连续段，并从该段中的所有数字减去相同的非负值。你可以执行多次（可能为零次）这样的操作，但不得选择两个相交且不包含彼此的段。目标是将初始值在 $[l, r]$ 范围内的所有数字转换为 $0$，并且要使用最少的操作次数。请注意，查询是独立的，数组中的数字在查询之间会恢复到它们的初始值。 输入数据格式： 第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^6$)。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)。 接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，代表一个查询。 输出数据格式： 对于每个查询，输出一行表示该查询的答案。 公式（使用 LaTeX 格式）： 对于每个查询，你需要找到最小的 $m$，使得存在一个序列 $\{(x_j,y_j,z_j)\}_{j=1}^{m}$ 满足以下条件： 1. 对于任意 $1 \le j \le m$，有 $z_j \ge 0$ 和 $1 \le x_j \le y_j \le n$（这里 $[x_j, y_j]$ 对应于序列的段）； 2. 对于任意 $1 \le j < k \le m$，满足 $[x_j,y_j] \subseteq [x_k,y_k]$，或 $[x_k,y_k] \subseteq [x_j,y_j]$，或 $[x_j,y_j] \cap [x_k,y_k] = \varnothing$； 3. 对于任意 $1 \le i \le n$，如果 $l \le a_i \le r$，则满足 $a_i = \sum_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j$。