271ms

#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
using namespace std;
#define getcha()(S == T &&(T =(S = BB)+ fread(BB, 1, 1 << 21, stdin), S == T)? EOF : *S++)
char BB[1 << 21], *S = BB, *T = BB;
#define isint(a)((a >= '0')&&(a <= '9'))
inline int read(){
    int s = 0;
    char ch = getcha();
    while(!isint(ch))
        ch = getcha();
    while(isint(ch))
        s =(s << 3)+(s << 1)+(ch & 15), ch = getcha();
    return s;
}
const int maxn = 1000005;
int n;
int a[maxn];
struct node{
    int v, c;
} b[maxn];
int solve(){
    int ql = 1, qr = n, l = 1, r = 0, ans = 0, x, y, now, id;
    while(1){
        if(qr - ql + r - l == 0){
            ans = 1;
            break;
        }
        y = a[ql], ++ql;
        if((r < l)||(qr >= ql && a[qr] > b[l].v))
            x = a[qr], id = qr, --qr;
        else
            x = b[l].v, id = b[l].c, ++l;
        now = x - y;
        if(qr < ql || a[ql] > now){
            ans = qr - ql + r - l + 4;
            int cnt = 1;
            while(1){
                ++cnt;
                if(qr - ql + r - l == -1){
                    if(cnt & 1)
                        --ans;
                    break;
                }
                if((r < l)||(qr >= ql && a[qr] > b[l].v))
                    x = a[qr], id = qr, --qr;
                else
                    x = b[l].v, id = b[l].c, ++l;
                now = x - now;
                if(!((qr < ql || a[ql] > now)&&(r < l ||(b[r].v > now ||(b[r].v == now && b[r].c > id))))){
                    if(cnt & 1)
                        --ans;
                    break;
                }
            }
            break;
        } else{
            ++r, b[r].v = now, b[r].c = id;
        }
    }
    return ans;
}
int main(){
    int t;
    t = read(), n = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    printf("%d\n", solve());
    for(int kkk = 1, k, x, y; kkk < t; ++kkk){
        k = read();
        for(int i = 1; i <= k; ++i)
            x = read(), y = read(), a[x] = y;
        printf("%d\n", solve());
    }
    return 0;
}