超级【】的题，分类讨论。

PS：下文由 AI 组织语言（看之前写的东西时发现的，LG 有题了就搬来了）。

下文定义 \(S\) 为将前

\(x\) 个数按非递减序排序，\(T\) 为将后 \(

y\) 个数按非递减序排序。

  1. \(x+y \le n\)：
  • \(0\) 次操作：数组初始已有序。
  • 如果 \(x+y \le n\)，说明前缀 \(x\) 和后缀 \(y\) 完全没有重叠，中间还隔着 \(n-(x+y)\) 个元素。这意味着元素永远无法跨越区域移动。
    • 最多只需 \(1\) 次或 \(2\) 次操作就能排好序。
    • 如果 \(1\) 次或 \(2\) 次操作后仍未有序，则永远无法有序，返回 \(-1\)。
  1. \(x+y > n\)：存在长度为 \(z = x+y-n\) 的重叠区域。这个重叠区域是元素从左边运送到右边，或从右边运送到左边的唯一通道。每一次完整的 \(S\) 和 \(T\) 的循环，最多能将 \(z\) 个元素通过重叠区运送过去。

对每个阈值 \(k \in [1, n-1]\) 进行分析。将排序后数组的前 \(k\) 小的元素视为 \(0\)，其余视为 \(1\)。我们的目标是把所有的 \(0\) 移到前 \(k\) 个位置，所有的 \(1\) 移到后 \(n-k\) 个位置。

定义两个错位元素数量：

  • \(c_L(k)\)：在左侧区 \([1 \dots n-y]\) 中，不该在那里的 \(1\) 的数量。
  • \(c_R(k)\)：在右侧区 \([x+1 \dots n]\) 中，不该在那里的 \(0\) 的数量。

每次操作能运送 \(z\) 个元素，因此消除这些错位元素所需的基础操作趟数为：

  • \(m_L(k) = \lceil c_L(k) / z \rceil\)
  • \(m_R(k) = \lceil c_R(k) / z \rceil\)

对于特定的阈值 \(k\)，根据最后一次操作是 \(S\) 还是 \(T\)，以及 \(k\) 所处的区间，可以推导出所需的确切操作步数。

为了让数组完全有序，所有阈值 \(k\) 限制都必须被同时满足。对于任何一个 \(k\)，为了满足左右两端的容量要求，操作次数必须是 \(\max(f(k), g(k))\)。 因此，全局所需的最少操作数是：

\[\max_k \max(f(k), g(k)) \]

等价于：

\[\max( \max_k f(k), \max_k g(k) ) \]

因为 \(f(k)\) 是随着 \(k\) 单调递增的（受 \(getR\) 也就是右侧的 \(0\) 数量限制），它的最大值直接在区间右端点 \(k = x\) 处取到；同理，\(g(k)\) 是单调递减的（受 \(getL\) 即左侧的 \(1\) 数量限制），它的最大值直接在区间左端点 \(k = n-y\) 处取到。

结论：全域的瓶颈就是独立的四个极值点。

我们可以直接使用 \(O(1)\) 公式。

数据结构优化：

\(c_L(k)\) 和 \(c_R(k)\) 需计数某个区间内，排名 \(\le k\) 的元素个数。这可以通过建立的主席树来实现在 \(O(\log n)\) 时间内查询。

#include
#define int long long
using namespace std;
const int N=2e5+5;
int n,q,x,y,z;
int a[N];
int st[2][N][20];
int lg[N];
vector g;
inline int qry(int op,int l,int r){if(op==0)	return max(st[op][l][lg[r-l+1]],st[op][r-(1<<(lg[r-l+1]))+1][lg[r-l+1]]);return min(st[op][l][lg[r-l+1]],st[op][r-(1<<(lg[r-l+1]))+1][lg[r-l+1]]);
}
inline bool check(int l,int r){int u=upper_bound(g.begin(),g.end(),l)-g.begin();assert(g[u-1]<=l);return g[u]>r;
}
struct Node{int cnt;int l,r;
}tr[N*40];
int rt[N];
int tot=0;
int insert(int fa,int l,int r,int v){int p=++tot;tr[p]=tr[fa];tr[p].cnt++;if(l==r)	return p;int mid=l+r>>1;if(v<=mid)	tr[p].l=insert(tr[p].l,l,mid,v);else	tr[p].r=insert(tr[p].r,mid+1,r,v);return p;
}
int query(int p,int l,int r,int k){if(!p||k>1;return query(tr[p].l,l,mid,k)+query(tr[p].r,mid+1,r,k);
}
inline int getL(int k){if(n==y)	return 0;return n-y-query(rt[n-y],1,n,k);
}
inline int getR(int k){if(n==x)	return 0;return k-query(rt[x],1,n,k);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];int fl=1,fr=n;while(fl=a[fl])	fl++;while(fr>1&&a[fr-1]<=a[fr])	fr--;g.push_back(1);for(int i=2;i<=n;i++)if(a[i]>1]+1;for(int j=1;j<=lg[n];j++)for(int i=1;i<=n-(1< > _a;vector p(n+1);for(int i=1;i<=n;i++)_a.push_back(make_pair(a[i],i));sort(_a.begin(),_a.end());for(int i=1;i<=n;i++)p[_a[i-1].second]=i;for(int i=1;i<=n;i++)rt[i]=insert(rt[i-1],1,n,p[i]);while(q--){cin>>x>>y;if(x+y<=n){if(x+y==n){if(qry(0,1,x)<=qry(1,n-y+1,n)){int res=0;if(x>fl)	res++;if(n-y+1fl)	res++;if(n-y+1