voidcalc(int st){ memset(eaten, 0, sizeof(eaten)); int ans = st + 1; for (int i = st; i; i--) { eaten[c[i]] = i; if (eaten[b[i]] && eaten[b[i]] < ans) { ans = i; } } printf("%d\n", n - ans + 1); }
voidsolve(){ h1 = h2 = 1; t1 = t2 = 0; bool flag = 0; for (int i = n; i; i--) q1[++t1] = mp(a[i], i); for (int i = 1; i < n; i++) { pii mx = getmx(), mn = getmn(); pii nowmn = min(h1<=t1?q1[t1]:mp(inf, inf), h2<=t2?q2[t2]:mp(inf, inf)); pii now = mp(mx.fi-mn.fi, mx.se); b[i] = mx.se; c[i] = mn.se; if (now < nowmn) flag = 1; if (flag && now >= nowmn) { calc(i-2); return; } q2[++t2] = now; } calc(n-1); }
intmain(){ read(ttt); ttt--; read(n); for (int i = 1; i <= n; i++) read(a[i]); solve(); for (int i = 1; i <= ttt; i++) { read(k); for (int j = 1, x, y; j <= k; j++) { read(x); read(y); a[x] = y; } solve(); } return0; }