AquaMoon 为 RiverHamster 提供整数序列 $$$a_1,a_2,\dots,a_n$$$,RiverHamster 为您提供 $$$q$$$ 查询。每个查询由两个整数$$$l$$$和$$$r$$$表示。
对于每个单独的查询,您可以获取序列的任何连续段,并从该段的所有数字中减去相同的非负值。您可以多次(可能零次)执行此操作。但是,您不能选择两个互不包含的相交线段。您的目标是将初始值在 $$$[l, r]$$$ 范围内的所有数字转换为 $$$0$$$。您必须以最少的操作次数来完成此操作。
请注意,查询是独立的,数组中的数字在查询之间恢复为其初始值。
正式地,对于每个查询,您要找到最小的$$$m$$$,使得存在满足以下条件的序列$$$\{(x_j,y_j,z_j)\}_{j=1}^{m}$$$:
- 对于任何 $$$1 \le j \leq m$$$、$$$z_j \ge 0$$$ 和 $$$1 \le x_j \le y_j \leq n$$$ (这里 $$$[x_j, y_j]$$$ 对应于序列的片段);
- 对于任何 $$$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}]=\var什么都没有$$$;
- 对于任何 $$$1 \le i \le n$$$,使得 $$$l \le a_i \leq r$$$,$$$$$${\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j 成立。 }$$$$$$
输入
第一行包含两个整数 $$$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$$$),代表一个查询。
输出
对于每个查询,在单独的行上输出该查询的答案。
示例
输入 #1
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
输出 #1
8 1 1 3 5 3 1 0
输入 #2
3 1 1 3 2 1 3
输出 #2
3
注意
在第一个测试用例中,考虑第二个查询,当 $$$l = 2$$$、$$$r = 2$$$ 时。要操作的元素是$$$[a_3, a_5, a_{10}] = [2, 2, 2]$$$。应用运算序列 $$$\{(2, 10, 2)\}$$$ 就足够了。
考虑第四个查询,当 $$$l = 2$$$、$$$r = 3$$$ 时。要操作的元素是$$$[a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]$$$。应用运算序列 $$$\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}$$$ 就足够了。
在第二个测试用例中,请注意操作序列 $$$\{(1, 2, 1), (2, 3, 2)\}$$$ 无效,因为两个线段相交,但都不包含在另一个线段内。