题目描述

给定一个 $1\sim N$ 的排列：

$$P[1],P[2],\ldots,P[N].$$

排列中的一个环定义为一个序列：

$$i_1,i_2,\ldots,i_k$$

满足：

$$i_2=P[i_1],\quad i_3=P[i_2],\quad \ldots,\quad i_k=P[i_{k-1}],\quad i_1=P[i_k].$$

一个区间 $[x,y]$ 被称为好区间，如果存在一个长度为 $y-x+1$ 的环 $i_1,i_2,\ldots,i_{y-x+1}$，使得 $x,x+1,\ldots,y$ 中的每个数都在这个环中恰好出现一次。

也就是说，区间 $[x,y]$ 内的所有位置最终应构成一个完整的环。

一次操作可以选择两个位置 $i,j$，交换 $P[i]$ 和 $P[j]$。

现在有 $Q$ 个询问。每个询问给出 $x,y$，你需要求出：

至少需要对原排列进行多少次交换，才能使区间 $[x,y]$ 变成好区间。

注意：所有询问互相独立。也就是说，为某个询问进行的交换不会保留到下一个询问中。

另外，对于询问 $[x,y]$，允许交换区间内元素和区间外元素。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含 $N$ 个整数，表示排列 $P[1],P[2],\ldots,P[N]$。

接下来 $Q$ 行，每行包含两个整数 $x,y$，表示一个询问。

输出格式

输出 $Q$ 行，每行一个整数，表示对应询问的答案。

数据范围

• $1\le N,Q\le 300\,000$；
• $1\le x\le y\le N$。

子任务

子任务	分值	限制
1	2	$P[i]=i$
2	11	$Q=1$
3	9	$N,Q\le 7$
4	18	$x=1$
5	40	$N,Q\le 100\,000$
6	20	无额外限制

样例

输入

5 3
4 1 2 3 5
2 4
1 4
1 5

输出

1
0
1

样例解释

对于区间 $[2,4]$，只需交换位置 $1$ 和位置 $2$，即可使该区间成为好区间。

区间 $[1,4]$ 已经是好区间，因此答案为 $0$。

对于区间 $[1,5]$，需要一次交换，例如交换位置 $1$ 和位置 $5$。