对于一个长为 $N(N\ge 2)$ 的数组 $a$ ，定义一次区间旋转为，选择任意的一个长度不小于 $2$ 的区间 $[l,r],(1\le l< r\le N)$，将区间中除 $a_l$ 以外的所有数向左移动一个位置，并向旋转前 $a_r$ 所在的位置填入旋转前 $a_l$ 的值，也就是将 $(a_l,a_{l+1},\cdots,a_{r-1},a_r)$ 替换为 $(a_{l+1},a_{l+2},\cdots,a_r,a_l)$。

现在给定一个长为 $n$ 的数组 $b$。共有 $q$ 次询问，其中第 $i$ 次询问的数组 $a$ 为数组 $b$ 的一个区间 $[l_i,r_i]$，也就是，令 $a$ 为一个长度为 $r_i-l_i+1$ 的数组，其中 $a_j=b_{l_i+j-1} (1\le j\le r_i-l_i+1)$。对于每次询问，求让这次询问的 $a$ 数组单调不减需要的最小区间旋转操作次数。

注:如果一个长度为 $N$ 的数组 $a$，对于任意的 $1\le i\le N-1$，都有 $a_i\le a_{i+1}$，则称数组 $a$ 单调不减。

第一行为两个整数 $n,q(2\le n\le 5\times 10^5,1\le q\le 5\times 10^5)$，分别表示数组 $b$ 的长度和询问次数。

第二行为 $n$ 个整数 $b_1,b_2,\cdots,b_n(1\le b_i\le 10^9)$，表示数组 $b$ 中每个数的值。

接下来 $q$ 行，每行两个整数 $l_i,r_i(1\le l_i< r_i\le n)$，表示第 $i$ 次询问的区间左端点和右端点。

共 $q$ 行，第 $i$ 行为一个整数，表示第 $i$ 次询问的答案。

第一次询问的数组 $a$ 为 $(3,2,4,1)$。一种使数组 $a$ 单调不减的方式为：

第 $1$ 次旋转区间 $[1,4]$，数组 $a$ 变为 $(2,4,1,3)$。
第 $2$ 次旋转区间 $[1,3]$，数组 $a$ 变为 $(4,1,2,3)$。
第 $3$ 次旋转区间 $[1,4]$，数组 $a$ 变为 $(1,2,3,4)$。

第二次询问的数组 $a$ 为 $(5,3,1,3)$。一种使数组 $a$ 单调不减的方式为：

第 $1$ 次旋转区间 $[2,3]$，数组 $a$ 变为 $(5,1,3,3)$。
第 $2$ 次旋转区间 $[1,4]$，数组 $a$ 变为 $(1,3,3,5)$。

可以证明不存在使区间旋转次数更小的操作方法。