样例过了，但是只AC#1

思路简述：回滚莫队

用结构体ask[N]存储加点信息，更新左右端点

回滚$l$时用bc[N]结构体保存第一次修改前的ask

测试下载数据#2时，部分数据正确，剩余部分偏大

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 20;
ll n, m, a[N], ans[N];
ll b[N], pos[N], len = 0;
ll belong[N], siz, bnum = 0, bl[N], br[N];
struct query{
	ll l, r, id;
}q[N], ask[N], ask2[N], bc[N];
bool cmp(query a, query b) {
	return belong[a.l] == belong[b.l] ? a.r < b.r : a.l < b.l;
}
int main(){
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	scanf("%lld", &n);
	siz = sqrt(n);
	bnum = ceil((double)n / siz);
	for(int k = 1; k <= bnum; k++) {
		bl[k] = siz * (k-1) + 1;
		br[k] = siz * k;
		for(int i = bl[k]; i <= br[k]; i++) belong[i] = k;
	}
	br[bnum] = n;
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	len = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; i++) pos[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
	scanf("%lld", &m);
	for(int i = 1; i <= m; i++) {
		ll l, r;
		scanf("%lld%lld", &l, &r);
		q[i] = (query){l, r, i};
	}
	sort(q + 1, q + m + 1, cmp);
	ll i = 1;
	for(int k = 0; k <= bnum; k++) {
		ll l = br[k]+1, r = br[k];
		ll now = 0;
		memset(ask, 0, sizeof(ask));
		for(; belong[q[i].l] == k; i++){
			ll ql = q[i].l, qr = q[i].r;
			ll tmp = 0;
			if(belong[ql] == belong[qr]) {
			for(int j = ql; j <= qr; j++) ask2[pos[j]].l = ask2[pos[j]].r = 0;
			for(int j = ql; j <= qr; j++) {
				if(ask2[pos[j]].l == 0) ask2[pos[j]].l = j;
				ask2[pos[j]].r = j;
				tmp = max(tmp, ask2[pos[j]].r - ask2[pos[j]].l);
			}
			ans[q[i].id] = tmp;
			continue;
		}
			while(r < qr) {
				if(ask[pos[++r]].l == 0) ask[pos[r]].l = r;
				ask[pos[r]].r = r;
				now = max(now, ask[pos[r]].r - ask[pos[r]].l);
			}
			tmp = now;
			while(ql < l) {
				if(ask[pos[--l]].r == 0) {
					if(bc[pos[l]].r == 0) bc[pos[l]].r = ask[pos[l]].r;
					ask[pos[l]].r = l;
					
				}
				if(bc[pos[l]].l == 0) bc[pos[l]].l = ask[pos[l]].l;
				ask[pos[l]].l = l;
				now = max(now, ask[pos[l]].r - ask[pos[l]].l);
			}
			ans[q[i].id] = now;
			now = tmp;
			while(l < br[k] + 1) {
				if(bc[pos[l]].l != 0) ask[pos[l]].l = bc[pos[l]].l, bc[pos[l]].l = 0;
				if(bc[pos[l]].r != 0) ask[pos[l]].r = bc[pos[l]].r, bc[pos[l]].r = 0;
				l++;
			}
		}
		}
		

	for(int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	return 0;
}