时空限制

2S/512M

题目描述

给定一个长度为 $n$ 的整数数列 $A$。

如果对于 $L\leq i<R$ 的每个 $i$，都有 $A_{i+1}=A_i+1$，那么称区间 $[L,R]$ 为连续区间。

你可以执行以下操作任意多次：

• 选择下标 $i$ 满足 $1\leq i\leq n$，令 $A_i=x$，这里 $x$ 可以是任意整数（不需要满足 $1\leq x\leq n$）。

定义 $f(L,R)$ 为使得区间 $[L,R]$ 成为连续区间所需的最少修改次数。

进行 $m$ 次询问，每次询问给定两个整数 $L_i,R_i$，求 $f(L_i,R_i)$。注意询问是独立的，每次询问不会修改原数组中的值。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示数列 $A$ 的长度和询问的数量。

第二行包含 $n$ 个整数 $A_i$。

接下来 $m$ 行每行包含两个整数 $L_i,R_i$，表示求 $f(L_i,R_i)$。

输出格式

输出 $m$ 行，每行一个整数表示 $f(L_i,R_i)$。

样例

样例输入 #1

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

样例输出 #1

2
2
0
3

样例解释 #1

对于第 $1$ 个询问，可以将 $A_2$ 修改为 $3$，将 $A_4$ 修改为 $5$。

对于第 $2$ 个询问，可以将 $A_3$ 修改为 $2$，将 $A_6$ 修改为 $5$。

对于第 $3$ 个询问，可以不修改。

对于第 $4$ 个询问，可以将 $A_3$ 修改为 $-2$，将 $A_4$ 修改为 $-1$，将 $A_5$ 修改为 $0$。

数据规模

对于 $30\%$ 的数据，$n,m\leq 1000$。

另有 $10\%$ 的数据，$|A_i-i|\leq 500$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq A_i\leq n$，$1\leq L_i\leq R_i\leq n$。