满分解法（100 分）

一次操作会移动许多元素，但可选的区间只有两个。我们先确定操作序列的形状，再统计必须经过两段交集的元素数量，就能直接算出操作次数。

给相等元素确定一致的目标位置

按二元组 $(x_i,i)$ 从小到大排序，把每个元素替换为它在这个顺序中的排名 $p_i$。于是 $p$ 是 $1,2,\ldots,n$ 的排列，目标变为让每个位置满足 $p_i=i$。

这里不能把相等的值压成同一个排名。给相等元素按原下标编号，可以明确它们各自的目标位置，同时不改变答案：一次区间排序总可以视为稳定排序，因为相等元素交换身份不会改变数值数组。稳定的连续区间排序不会改变任意两个相等元素的先后关系，所以整个数组排好后，它们也恰好按原下标排列。对任意操作序列，原数值数组有序，当且仅当这样标号后的排列成为恒等排列。

以下全部使用排名，并采用 $1$ 基下标。记排序前缀的操作为 $P$，排序后缀的操作为 $S$。同一种操作连续做两次，第二次不会改变数组，删去即可。因此最优序列一定可以取成交替序列，只需考虑起始操作和终止操作的四种组合。

先处理零次、一次和互不相交的情况

对询问 $(a,b)$，令

$$L=n-b,\qquad R=a.$$

$P$ 操作区间 $[1,R]$，$S$ 操作区间 $[L+1,n]$。预处理两个与询问无关的量：

$$W(t)=\#\{i\le t:p_i\ne i\},\qquad D(t)=\#\{i\le t:p_i>t\}.$$

$W(t)$ 统计前缀中尚未处于目标位置的元素。$D(t)$ 统计跨过切口 $t$ 后应该向右移动的元素数。由于前 $t$ 个目标排名恰有 $t$ 个，它也等于 $\#\{i>t:p_i\le t\}$，即应该从切口右侧移到左侧的元素数。定义 $W(0)=D(0)=0$。

若 $W(n)=0$，答案为 $0$。否则，只排序前缀能够成功，当且仅当它不触及的后缀已经逐位置正确，即 $W(n)=W(R)$；只排序后缀能够成功，当且仅当 $W(L)=0$。这些条件也充分，因为未动部分正确后，剩下部分的元素集合已经被唯一确定，排序即可复原。

接着考虑 $R\le L$。两个操作区间不相交，各做一次以后再做也没有效果。可行的充要条件是

$$D(R)=D(L)=0,\qquad W(L)=W(R).$$

前两个条件保证前缀和后缀各自拥有正确的元素集合，最后一个条件保证无人能修改的中间区间 $[R+1,L]$ 已经逐位置正确。满足时答案为 $2$，否则为 $-1$；零次和一次已经提前处理。$R=L$ 时中间区间为空，最后一个条件自动成立。

交集是一条容量固定的搬运通道

现在 $R>L$，令交集长度

$$c=R-L=a+b-n>0.$$

数组分为左侧独占区间 $[1,L]$、交集 $[L+1,R]$、右侧独占区间 $[R+1,n]$。只有 $P$ 能修改左侧独占区间，只有 $S$ 能修改右侧独占区间。元素在两侧之间移动时必须经过长度为 $c$ 的交集。

定义两类最远端的缺失量：

$$U=\#\{i>R:p_i\le L\},\qquad V=\#\{i\le L:p_i>R\}.$$

$U$ 是应该进入左侧、却还在最右侧的元素数；$V$ 是应该进入右侧、却还在最左侧的元素数。

从前缀开始、以后缀结束

这样的交替序列写成 $P(SP)^kS$，共有 $2k+2$ 次操作。

第一次 $P$ 将当前前缀中所有排名不超过 $L$ 的元素放到左侧独占区间。这时恰好缺少的就是原先位于 $R$ 之后的 $U$ 个小排名；它们全部位于后缀中。

随后一次 $S$ 会把后缀中最小的元素放到交集，因而带来 $\min(c,U)$ 个尚缺的小排名；紧接着的 $P$ 把它们放入左侧。已经进入左侧的小排名不会再被后续操作挤走：它们不受 $S$ 影响，在 $P$ 中也始终排在其他元素前面。

所以每个 $SP$ 恰好把缺失量减少 $\min(c,\text{当前缺失量})$。经过 $\lceil U/c\rceil$ 轮，左侧独占区间的集合及顺序都正确，最后一次 $S$ 将其余元素排序。反过来，初始的 $U$ 个元素只能通过这些非末尾的 $S$ 被送入交集，每轮至多送入 $c$ 个，少一轮必然不够。因此这一类的最少次数为

$$2\left\lceil\frac{U}{c}\right\rceil+2.$$

交换左右、小排名与大排名，可得从 $S$ 开始、以 $P$ 结束时的最少次数为 $2\lceil V/c\rceil+2$。

从前缀开始，也以前缀结束

这样的序列写成 $(PS)^kP$，共有 $2k+1$ 次操作。最后一个 $P$ 无法修改右侧，因此最后之前必须把所有大于 $R$ 的排名送到右侧独占区间。

初始前缀中有 $D(R)$ 个这样的大排名。每次 $P$ 把其中最大的至多 $c$ 个放到交集，随后 $S$ 将它们放进右侧。右侧原有的大排名也会继续留在右侧：全局只有 $n-R$ 个这样的排名，右侧独占区间正好容纳得下。于是每轮恰好送出 $\min(c,\text{剩余数量})$ 个，既达到通道容量的上界，也不会丢失此前的进展。

需要的轮数为 $\lceil D(R)/c\rceil$。不过已经排除了零次和一次操作；即使 $D(R)=0$，右侧也可能只是集合正确而内部无序，仍须至少执行一次 $S$。因此这一类的最少次数为

$$2\max\left(1,\left\lceil\frac{D(R)}{c}\right\rceil\right)+1.$$

对称地，从 $S$ 开始并以 $S$ 结束时，把 $D(R)$ 换成 $D(L)$。

至此，所有可能的最优交替序列都已覆盖：

起始操作	终止操作	最少次数（已排除零次和一次）
$P$	$S$	$2\lceil U/c\rceil+2$
$S$	$P$	$2\lceil V/c\rceil+2$
$P$		$2\max(1,\lceil D(R)/c\rceil)+1$
$S$		$2\max(1,\lceil D(L)/c\rceil)+1$

取四者最小值即可。因为向上取整单调，实现中可以分别合并两个偶数方案和两个奇数方案：

$$E=2\left\lceil\frac{\min(U,V)}{c}\right\rceil+2,\qquad O=2\max\left(1,\left\lceil\frac{\min(D(L),D(R))}{c}\right\rceil\right)+1.$$

答案为 $\min(E,O)$。当 $c>0$ 时这些搬运过程总能完成，所以不会无解。

例如排列 $[4,5,6,1,2,3]$，取 $a=b=4$，则 $L=2,R=4,c=2$。有 $U=V=1$、$D(L)=D(R)=2$，偶数方案至少需要 $4$ 次，奇数方案只需 $3$ 次。执行 $P,S,P$ 的过程是

$$[4,5,6,1,2,3] \longrightarrow[1,4,5,6,2,3] \longrightarrow[1,4,2,3,5,6] \longrightarrow[1,2,3,4,5,6].$$

中间一次 $S$ 已将大排名 $5,6$ 固定在右侧，最后的 $P$ 只需排好剩余部分。这也说明不能只计算固定起点或固定奇偶性的操作次数。

将每个询问压缩成两个前缀计数

$W$ 直接做前缀和。计算 $D$ 也不需要数据结构：若 $p_i>i$，这个元素恰好对切口 $i,i+1,\ldots,p_i-1$ 各贡献 $1$，其余元素没有贡献。因此对这些区间作差分，再求前缀和，就得到全部 $D(t)$。

剩下的 $U,V$ 涉及位置和排名两个条件。定义

$$C(s,t)=\#\{i\le s:p_i\le t\}.$$

全局排名不超过 $L$ 的元素共有 $L$ 个，前 $L$ 个位置也恰有 $L$ 个元素，因此

$$U=L-C(R,L),\qquad V=L-C(L,R).$$

每个询问只需两个 $C$。将计数请求按位置前缀长度 $s$ 分到 $0,1,\ldots,n$ 的桶中，从左到右扫描排列。处理桶 $s$ 前，先把位置 $s$ 的排名加入维护频次的树状数组，此时树中恰好包含前 $s$ 个位置的元素；查询排名前缀 $[1,t]$ 就得到 $C(s,t)$。桶 $0$ 在任何插入之前处理，树状数组的前缀 $0$ 返回 $0$，自然覆盖 $L=0$ 的边界。

保存每个请求对应的原询问编号，扫描结束后依次代入前面的判定和公式输出，不需要模拟任何排序操作。

时间复杂度为 $O((n+q)\log n)$：稳定排名排序耗时 $O(n\log n)$，差分和位置分桶是线性的，树状数组进行 $n$ 次修改和 $2q$ 次查询。这里 $n=1$ 时所有操作直接为常数成本。

空间复杂度为 $O(n+q)$，用于排名、前缀统计、树状数组、询问及计数请求。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct fenwick {
  int n;
  vector<int> tr;

  fenwick(int n) : n(n), tr(n + 1) {}

  void add(int x, int v) {
    for (; x <= n; x += x & -x) tr[x] += v;
  }

  int sum(int x) const {
    int res = 0;
    for (; x > 0; x -= x & -x) res += tr[x];
    return res;
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n), ord(n), rk(n);
  for (int& x : a) cin >> x;
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return pair{a[i], i} < pair{a[j], j};
  });
  for (int i = 0; i < n; i++) rk[ord[i]] = i + 1;

  vector<int> pre(n + 1), cross(n + 1);
  for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + (rk[i] != i + 1);
    if (rk[i] > i + 1) {
      cross[i + 1]++;
      cross[rk[i]]--;
    }
  }
  for (int i = 1; i <= n; i++) cross[i] += cross[i - 1];

  vector<pair<int, int>> queries(q);
  vector<vector<pair<int, int>>> events(n + 1);
  for (int i = 0; i < q; i++) {
    int r, b;
    cin >> r >> b;
    int l = n - b;
    queries[i] = {l, r};
    events[r].push_back({l, 2 * i});
    events[l].push_back({r, 2 * i + 1});
  }

  fenwick fw(n);
  vector<int> cnt(2 * q);
  for (int i = 0; i <= n; i++) {
    if (i > 0) fw.add(rk[i - 1], 1);
    for (auto [value, id] : events[i]) cnt[id] = fw.sum(value);
  }

  for (int i = 0; i < q; i++) {
    auto [l, r] = queries[i];
    if (pre[n] == 0) {
      cout << 0 << '\n';
      continue;
    }
    if (pre[l] == 0 || pre[n] == pre[r]) {
      cout << 1 << '\n';
      continue;
    }
    int len = r - l;
    if (len <= 0) {
      bool ok = cross[l] == 0 && cross[r] == 0 && pre[l] == pre[r];
      cout << (ok ? 2 : -1) << '\n';
      continue;
    }
    int low = l - cnt[2 * i];
    int high = l - cnt[2 * i + 1];
    auto rounds = [&](int x) {
      return x / len + (x % len != 0);
    };
    int even = 2 * rounds(min(low, high)) + 2;
    int odd = 2 * max(1, rounds(min(cross[l], cross[r]))) + 1;
    cout << min(even, odd) << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}