满分解法（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();
}

逐询问统计搬运量（通过子任务 1–3、5–6，共 53 分）

适用于 $n,q\le 5000$，同时能够快速处理所有两段不相交的询问，覆盖子任务 $1,2,3,5,6$。排列限制并非必需：只要给相等元素确定稳定的目标位置，同一方法也能处理重复值。

从排序过程变成搬运次数

按 $(x_i,i)$ 排序，赋予元素不同的排名 $p_i\in[1,n]$。相等元素按原位置标号；每次操作都可视为稳定排序，不改变数值结果，也不改变相等元素的相对顺序。因此目标是 $p_i=i$。

对于询问，令 $L=n-b,R=a$，前缀操作记为 $P$，后缀操作记为 $S$。预处理

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

$W$ 是普通前缀和。每个满足 $p_i>i$ 的元素对 $D(i),\ldots,D(p_i-1)$ 贡献 $1$，故区间差分后求前缀和就能得到整个 $D$。$D(t)$ 也等于切口右侧缺失的小排名数量 $\#\{i>t:p_i\le t\}$。空前缀的两项统计均为 $0$。

若 $W(n)=0$，答案为 $0$。否则，若 $W(L)=0$ 或 $W(n)=W(R)$，其中一种操作未触及的部分已经正确，答案为 $1$。

若 $R\le L$，两段不相交。各段最多排序一次，必须满足各段元素集合正确、中间位置正确，即 $D(R)=D(L)=0$ 且 $W(L)=W(R)$。满足则答案为 $2$，否则为 $-1$。

逐次扫描统计有交集的询问

现在令 $c=R-L>0$。直接扫描原排列，计算

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

连续执行两次相同排序没有意义，所以最优操作交替出现，只需考虑四种起止组合。

对于 $P(SP)^kS$，第一次 $P$ 将前缀中已有的小排名放到左侧。还在最右侧的 $U$ 个小排名，需要由后续 $S$ 放进交集，再由 $P$ 放进左侧。每轮交集至多容纳 $c$ 个；又因为小排名总是排在前面，每轮实际恰好转移 $\min(c,\text{剩余数量})$ 个。左侧已经收到的正确小排名不会再丢失。因此需要 $\lceil U/c\rceil$ 轮，最后再用 $S$ 排好其余部分，总次数为 $2\lceil U/c\rceil+2$。反向起点的偶数方案对称地使用 $V$。

对于 $(PS)^kP$，最后一个 $P$ 不动右侧，必须先把初始前缀中的 $D(R)$ 个大于 $R$ 的排名送入右侧。每次 $P$ 将至多 $c$ 个最大排名放在交集，接着 $S$ 把它们送入右侧；已经送入的大排名始终留在右侧。每轮同样转移满容量或全部剩余元素，因此需要 $\lceil D(R)/c\rceil$ 轮。零次和一次已提前排除，即使缺失量为零，也至少要一次 $S$ 整理右侧的内部顺序。另一种奇数方案对称地使用 $D(L)$。

合并两个偶数方案、两个奇数方案，得到

$$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)$。容量给出了轮数下界，实际排序每轮都能达到该容量，故这些次数既可行又最少。

例如 $[4,5,6,1,2,3]$ 配合 $a=b=4$，有 $L=2,R=4,c=2$，$U=V=1$、$D(L)=D(R)=2$。偶数方案需要 $4$ 次，而 $P,S,P$ 三步依次得到 $[1,4,5,6,2,3]$、$[1,4,2,3,5,6]$、$[1,2,3,4,5,6]$，所以答案为 $3$。

时间复杂度为 $O(n\log n+q+nq_{\mathrm{overlap}})$，其中 $q_{\mathrm{overlap}}$ 表示未被零次或一次判定直接解决的有交集询问数，最坏为 $O(n\log n+nq)$。只有计算 $U,V$ 需要扫描；所有不相交询问均为常数时间，因此也能处理子任务 $3$ 的大规模输入。

空间复杂度为 $O(n)$。

参考代码（C++20）

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

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];
  while (q--) {
    int r, b;
    cin >> r >> b;
    int l = n - b;
    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 = 0, high = 0;
    for (int i = r; i < n; i++) low += rk[i] <= l;
    for (int i = 0; i < l; i++) high += rk[i] > r;
    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();
}

二值数组的前缀计数（通过子任务 4，共 14 分）

适用于 $x_i\in\{1,2\}$，覆盖子任务 $4$。两种数的出现顺序能够直接给出目标排名，也能用一个前缀计数回答位置与排名的联合统计。

二值数组的稳定排名

设全数组共有 $m$ 个 $1$，$Z(s)$ 表示前 $s$ 个位置中 $1$ 的数量。把所有 $1$ 按出现顺序编号为 $1,\ldots,m$，把所有 $2$ 按出现顺序编号为 $m+1,\ldots,n$。这样得到排名排列 $p$：

$$p_i=\begin{cases} Z(i),&x_i=1,\\ m+i-Z(i),&x_i=2. \end{cases}$$

这相当于按 $(x_i,i)$ 排序后的稳定排名。区间排序可以视为稳定排序，既不改变数值结果，也不会使相等元素互相越过，故排序完成恰好对应 $p_i=i$。

定义 $C(s,t)=\#\{i\le s:p_i\le t\}$，其中 $0\le s,t\le n$，并令 $Z(0)=0$。前 $s$ 个位置出现的 $1$，恰好是全部 $1$ 中最先出现的 $Z(s)$ 个；$2$ 也有相同性质。因此

$$C(s,t)=\begin{cases} \min(Z(s),t),&t\le m,\\ Z(s)+\min(s-Z(s),t-m),&t>m. \end{cases}$$

一次这样的计数只需常数时间。例如二值数组 $[2,1,2,1,1]$ 有 $m=3$，稳定排名为 $[4,1,5,2,3]$。取 $s=3,t=4$，前缀含一个 $1$、两个 $2$，而排名上限只允许第一个 $2$，所以 $C(3,4)=1+\min(2,1)=2$。

按交集容量计算排序次数

令 $L=n-b,R=a$。预处理错位数量前缀 $W(t)=\#\{i\le t:p_i\ne i\}$，以及跨切口数量

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

空前缀的统计为 $0$。若 $W(n)=0$，输出 $0$。否则，若 $W(L)=0$ 或 $W(n)=W(R)$，后缀排序或前缀排序未触及的部分已经正确，只需一次。未触及部分正确，也就保证另一部分含有正确的元素集合。

当 $R\le L$，两端操作互不相交，不能交换元素。各段集合正确等价于 $D(R)=D(L)=0$，中间不动位置正确等价于 $W(L)=W(R)$。三者满足则输出 $2$，否则输出 $-1$。

当 $c=R-L>0$，记前缀排序为 $P$、后缀排序为 $S$。重复同一种排序没有效果，因此最优方案交替操作。定义

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

$U$ 是在位置 $R$ 之后、却应该进入前 $L$ 个位置的小排名数；$V$ 是在前 $L$ 个位置、却应该进入位置 $R$ 之后的大排名数。

对于偶数方案 $P(SP)^kS$，第一次 $P$ 放好前缀中已有的小排名。其余 $U$ 个小排名每轮由 $S$ 送入交集，再由 $P$ 固定到左侧。交集大小为 $c$，每轮最多带入 $c$ 个；由于它们小于所有非目标元素，每轮排序也确实带入 $\min(c,\text{尚缺数量})$ 个，已放好的元素不会丢失。故 $k=\lceil U/c\rceil$。另一种偶数方案对称地使用 $V$。

对于奇数方案 $(PS)^kP$，初始前缀中有 $D(R)$ 个大排名需要进入右侧独占区间。每次 $P$ 将其中最大的至多 $c$ 个置于交集，随后 $S$ 把它们固定到右侧，已经进入的大排名不会被挤回。需要 $\lceil D(R)/c\rceil$ 轮。已排除一次操作，因此还要保证 $k\ge1$，以便整理右侧的内部顺序。另一种奇数方案对称地使用 $D(L)$。

因此计算

$$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)$。这些轮数既满足搬运容量的必要下界，又能由上述交替排序达到。

时间复杂度为 $O(n+q)$，前缀计数、排名及错位统计均在线性时间建立，每个询问只作常数次计算。

空间复杂度为 $O(n)$。该实现利用了只有 $1,2$ 两种值的条件；存在其他值时，上述排名与 $C(s,t)$ 公式不再适用。

参考代码（C++20）

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

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n), pre_one(n + 1);
  for (int& x : a) cin >> x;
  for (int i = 0; i < n; i++) pre_one[i + 1] = pre_one[i] + (a[i] == 1);
  int ones = pre_one[n];
  auto count = [&](int pos, int value) {
    if (value <= ones) return min(pre_one[pos], value);
    return pre_one[pos] + min(pos - pre_one[pos], value - ones);
  };
  vector<int> pre(n + 1), cross(n + 1);
  for (int i = 1; i <= n; i++) {
    int rank = (a[i - 1] == 1 ? pre_one[i] : ones + i - pre_one[i]);
    pre[i] = pre[i - 1] + (rank != i);
    cross[i] = i - count(i, i);
  }
  while (q--) {
    int r, b;
    cin >> r >> b;
    int l = n - b;
    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 - count(r, l);
    int high = l - count(l, r);
    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();
}

互不相交的两段（通过子任务 1、3，共 13 分）

适用于所有询问均满足 $a+b\le n$，覆盖子任务 $1,3$。

两端的元素集合不会改变

令 $R=a,L=n-b$，则 $R\le L$。两个操作分别修改 $[1,R]$ 和 $[L+1,n]$，它们互不相交。因此每一端只需排序一次，中间区间 $[R+1,L]$ 永远保持原样。答案只可能是 $0,1,2,-1$。

为了精确判断每一端的集合是否正确，按 $(x_i,i)$ 从小到大赋予元素不同排名 $p_i\in[1,n]$。相等元素按原下标确定顺序，相当于把每次操作视为稳定排序；它们的数值相同，且在稳定的连续区间排序中不会互相越过。因此目标等价于 $p_i=i$。

预处理

$$W(t)=\#\{i\le t:p_i\ne i\},\qquad M(t)=\max_{i\le t}p_i,$$

并令 $W(0)=M(0)=0$。前 $t$ 个位置包含互不相同的 $t$ 个排名，所以它们的集合恰为 $\{1,\ldots,t\}$，当且仅当 $M(t)=t$。

按最少操作次数依次判断

若 $W(n)=0$，原数组有序，输出 $0$。

否则，若 $W(n)=W(R)$，后 $n-R$ 个位置已经逐一正确，只排序前缀即可；若 $W(L)=0$，只排序后缀即可。任一条件成立就输出 $1$。这些条件充分，是因为未改动部分正确后，另一部分必然含有恰好需要的元素。

剩下的情况只有两端都排序才能成功。需要同时满足

$$M(R)=R,\qquad M(L)=L,\qquad W(L)=W(R).$$

第一个条件保证前缀含有前 $R$ 个目标排名；第二个条件等价于后缀含有排名 $L+1,\ldots,n$；第三个条件保证中间不动的每个位置都正确。三者都成立时，两端分别排序就恢复整个排列，答案为 $2$，否则为 $-1$。当 $L=R$ 时没有中间位置，第三个条件自动成立。

本方法依赖两段不相交；允许交集时，元素可能借助交集转移，不再由初始两端集合单独决定可行性。

时间复杂度为 $O(n\log n+q)$，其中排名排序耗时 $O(n\log n)$，每个询问只需常数次前缀查询。

空间复杂度为 $O(n)$。

参考代码（C++20）

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

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), mx(n + 1);
  for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + (rk[i] != i + 1);
    mx[i + 1] = max(mx[i], rk[i]);
  }
  while (q--) {
    int r, b;
    cin >> r >> b;
    int l = n - b;
    if (pre[n] == 0) {
      cout << 0 << '\n';
    } else if (pre[l] == 0 || pre[n] == pre[r]) {
      cout << 1 << '\n';
    } else {
      bool ok = mx[r] == r && mx[l] == l && pre[l] == pre[r];
      cout << (ok ? 2 : -1) << '\n';
    }
  }
}

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

交替排序模拟（通过子任务 1–2，共 11 分）

适用于 $n,q\le 10$，覆盖子任务 $1,2$。

操作序列只剩两种起点

连续两次对同一个区间排序，第二次不会改变数组，可以删去。因此总存在一个最优方案，前缀排序与后缀排序交替进行。

对于每个询问，从原数组分别尝试“先排前缀”和“先排后缀”。确定第一步后，其后的操作已经唯一确定。实际执行每次排序，并与预先排好的目标数组比较；第一次相等时，记录当前操作次数。两个起点的结果取最小值。原数组已经有序时，两次模拟都直接得到 $0$。

如何判断继续模拟已经无用

记录连续多少次操作没有改变数组。如果连续两次都没有改变，说明在同一个数组上，前缀和后缀都已经有序；以后无论选择哪一种操作都不再变化。此时仍未达到目标，当前起点就无法成功。

这个停止条件不会漏掉一种“需要先等待几步”的方案：两种可用操作都已在当前状态上尝试过，而且都没有效果。

模拟也不会无限产生不同状态。一次连续区间排序，不改变该区间与外部元素之间的逆序对总数，却会消除区间内部的全部逆序对。只要数组发生变化，逆序对数量就严格减少。全数组至多有 $n(n-1)/2$ 个逆序对，且两次有效变化之间最多夹着一次无效操作，否则已经终止。

若两个起点均无法成功，输出 $-1$。无需枚举所有排列，也无需人为限制模拟步数。

时间复杂度为 $O(qn^3\log n)$：每个起点至多进行 $O(n^2)$ 次操作，每次排序及比较的成本不超过 $O(n\log n)$。这是直接由逆序对下降得到的上界，足以处理本子任务。

空间复杂度为 $O(n)$，用于原数组、目标数组和当前模拟状态。

参考代码（C++20）

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

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  vector<int> target = a;
  sort(target.begin(), target.end());
  while (q--) {
    int l, r;
    cin >> l >> r;
    auto run = [&](int turn) {
      vector<int> cur = a;
      int cnt = 0, idle = 0;
      while (cur != target) {
        vector<int> before = cur;
        if (turn == 0) {
          sort(cur.begin(), cur.begin() + l);
        } else {
          sort(cur.end() - r, cur.end());
        }
        cnt++;
        idle = (cur == before ? idle + 1 : 0);
        if (idle == 2) return INT_MAX / 2;
        turn ^= 1;
      }
      return cnt;
    };
    int ans = min(run(0), run(1));
    cout << (ans == INT_MAX / 2 ? -1 : ans) << '\n';
  }
}

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