题目说将 $[1, a]$ 或者 $[n-b+1, n]$ 进行排序，使得操作多次后，变成一个有序的东西，问操作最小值。

首先需要考虑的是，如何排序，使得 $[1, a]$ 和 $[n-b+1, n]$ 的操作排序是最优的。

很容易可以想到，第一关键字是值的大小，第二关键字是下标的大小。

考虑 $a < n - b + 1$ 的情况，此时两个点不具有交集。

那么一定需要保证 $[1, a]$ 中的元素，在 $[1, n]$ 排序后 $[1, a]$ 的元素相同。那么 $[n-b+1, n]$ 的要求也是这样的。还有一个条件就是 $[a+1, n-b]$ 中的元素是有序的。这个时候答案只可能在 $[-1, 2]$ 中。因为要么是不合法，要么就是 $[1, a]$ 或 $[n-b+1, n]$ 产生的贡献。

然后考虑 $a \ge n - b + 1$ 的情况，此时两个点具有交集，说明 $[a+1, n-b]$ 中可以交换元素。

有 $3$ 种情况需要考虑，最初最优，过程最优，结束最优。

我们发现过程最优就是两个操作交替着来，那么结束最优就只能是那么有序了。

对于最初最优，因为只有两种情况，我们可以直接枚举得到答案。

不妨考虑将答案为 $0$ 或 $1$ 的情况讨论出来。

当只用排零次时，很明显，就是需要保证 $[1, n]$ 有序。

只用排一次就是排一次 $[1, a]$ 或 $[n-b+1, n]$，当我们执行 $[1, a]$ 排序时，一定需要保证 $[a+1, n]$ 中的元素有序且在 $[1, n]$ 排序后的元素相同，同理可得执行 $[n-b+1,n]$ 排序的要求。

其他情况就是操作大于 $2$ 的时候了。

考虑把图画出来。

我们定义 $x_1$ 为原来在 $[1, a]$ 中，但排序后应该在 $[a+1,n]$ 中的元素个数；$x_2$ 为原来在 $[n-b+1,a]$ 中，但排序应该在 $[a+1, n]$ 中的元素个数。

然后定义 $y_1$ 为原来在 $[n-b+1, n]$ 中，但排序后应该在 $[1,n-b]$ 中的元素个数；$y_2$ 为原来在 $[n-b+1, a]$ 中，但是排序应该在 $[1, n-b]$ 中的元素个数。

考虑第一次排序的是区间 $[n-b+1, n]$。那么 $x_2$ 的元素也就在 $[a+1, n]$ 中了。那么对于 $[1, a]$ 中需要交换的元素也就变成了 $x_1-x_2$ 了，那么需要交换的次数为 $1+\frac{x_1-x_2}{a-n+b}$，这个 $1$ 是因为第 $2$ 轮才开始进行。但是因为是轮换，所以还需要乘 $2$，所以次数是 $1 + 2\frac{x_1-x_2}{a-n+b}$。同时， 从 $[n-b+1, n]$ 中需要到 $[1, a]$ 的元素执行轮数就是 $2\frac{y_1}{a-n+b}$，最终答案就是就是 $\max(2, \max(1 + 2\frac{x_1-x_2}{a-n+b}, 2\frac{y_1}{a-n+b}))$。

同理可得第一次排序的区间是 $[1, a]$ 的情况了。

最终答案就是：

$$\max(2, \min(\max(1 + 2\lceil\frac{x_1-x_2}{a-n+b}\rceil, 2\lceil\frac{y_1}{a-n+b}\rceil), \max(1+2\lceil\frac{y_1-y_2}{a-n+b}\rceil,2\lceil\frac{x_1}{a-n+b}\rceil))$$

可能会有些问题？

为什么要与 $2$ 进行比较？

可能出现一次就将所有元素归回排序后的区间的情况，但是存在区间不是有序的，所以需要和 $2$ 取最大值。

有一组样例，可以手模一下。

4 1
2 1 4 3
3 2

那这样不是错的吗？

当然不是错的呀，因为这是排序，不会存在无序的情况。

然后就做完了。

代码如下：

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

const int N = 2e5+10;
const int inf = 0x3f3f3f3f3f3f3f3f;

struct node {
	int x, id;
} b[N];

int n, Q;
int a[N];

int p[N];

int f[N];
int pre[N], suf[N];

inline int Ceil(int a, int b) {
	return (a + b - 1) / b;
}

bool cmp(node x, node y) {
	if (x.x != y.x) return x.x < y.x;
	return x.id < y.id;
}

int nowpos;
int ver[N];
int ls[N*30], rs[N*30], sum[N*30];

void copy(int a, int b) {
	ls[a] = ls[b], rs[a] = rs[b];
	sum[a] = sum[b];
}

int doBuild(int k, int l, int r) {
	nowpos = max(nowpos, k);
	if (l == r) {
		return k;
	}
	int mid = (l + r) >> 1;
	ls[k] = doBuild(k*2, l, mid);
	rs[k] = doBuild(k*2+1, mid+1, r);
	sum[k] = sum[k*2] + sum[k*2+1]; 
	return k;
} 

int doChange(int k, int l, int r, int x, int dx) {
	int now = ++nowpos;
	copy(now, k);
	if (l == r) {
		sum[now] = dx;
		return now;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) ls[now] = doChange(ls[now], l, mid, x, dx);
	else rs[now] = doChange(rs[now], mid+1, r, x, dx);
	sum[now] = sum[ls[now]] + sum[rs[now]];
	return now;
}

int doQuery(int k, int l, int r, int x, int y) {
	if (r < x || y < l) return 0;
	if (x <= l && r <= y) return sum[k];
	int mid = (l + r) >> 1;
	return doQuery(ls[k], l, mid, x, y) + doQuery(rs[k], mid+1, r, x, y);
}

int query(int a, int b, int x, int y) {
	return doQuery(ver[b], 1, n, x, y)-doQuery(ver[a-1], 1, n, x, y);
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	
	cin >> n >> Q;
	for (int i = 1;i<= n;i++) {
		cin >> a[i];
	}
	
	for (int i = 1;i<= n;i++) {
		b[i] = {a[i], i};
	}
	sort(b+1, b+n+1, cmp);
	
	for (int i = 1;i<= n;i++) {
		p[b[i].id] = i;
	}
	
	pre[0] = 0;
	for (int i = 1;i<= n;i++) {
		pre[i] = max(pre[i-1], p[i]);
	}
	suf[n+1] = inf;
	for (int i = n;i>= 1;i--) {
		suf[i] = min(suf[i+1], p[i]);
	}
	
	for (int i = 1;i<= n;i++) {
		if (a[i-1] <= a[i]) f[i] = f[i-1];
		else f[i] = i;
	}
	
	ver[0] = doBuild(1, 1, n);
	for (int i = 1;i<= n;i++) {
		ver[i] = doChange(ver[i-1], 1, n, p[i], 1);
	}
    
	int a, b, l, r;
	while (Q--) {
		cin >> l >> r;
		if (l < n - r + 1) {
			a = l, b = n - r + 1;
			if (!(pre[a] <= a && suf[b] >= b && f[b-1] <= a)) cout << -1 << '\n';
			else {
				int res = 0;
				if (f[a] > 1) res++;
				if (f[n] > b) res++;
				cout << res << '\n';
			} 
		} else {
			a = n - r + 1, b = l;
			
			if (f[n] <= 1) { cout << 0 << '\n'; continue; }
			if ((f[n] <= b+1 && suf[b+1] >= b+1) || (f[a-1] <= 1 && pre[a-1] <= a-1)) { cout << 1 << '\n'; continue; }
			
			int len = b - a + 1;
			
			int ltr = query(1, b, b+1, n);
			int mtf = query(a, b, b+1, n);
			
			int rtl = query(a, n, 1, a-1);
			int ftm = query(a, b, 1, a-1);
            
            cout << max(2, min(max(1 + Ceil(ltr-mtf, len) * 2, Ceil(rtl, len) * 2), max(1 + Ceil(rtl - ftm, len) * 2, Ceil(ltr, len) * 2))) << '\n';
		}
	}
	return 0;
}