这个题我花了1h过掉了luogu的数据，花了大概2h过掉了牛客的数据，因为做法貌似跟题解的做法都不太一样，所以写一篇题解。

看完这题以后，我首先想到的是海盗分金子的那个模型，猜测，回合和回合之间的决策之间会产生一条条影响的"链"，例如，如果模拟完以后的结果是这样的：

|回合| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|最大| 9 | 8 | 7 | 9 | 6 | * | * | * | * |
|最小| 1 | 2 | 3 | 4 | 9 | * | * | * | * |

那么我们单独看第4回合和第5回合。

第5回合中，死亡的蛇9，上一次决策的回合是4。

那么，回合5跟回合4就产生了"联系"，具体来说就是，第9条蛇，为了避免死亡，可能会在第4回合选择结束游戏。

进一步考虑，这些联系一定是若干条链（因为每个蛇只会被吃一次）。

那么我们随便拿一条链出来：

3-8-12-22

第22回合的蛇，一定会选择无脑吃，因为后续没有蛇会吃它。

那么第12回合的蛇，一定不敢吃，否则它会在22回合挂掉。

那么第8回合的蛇，一定敢吃，因为12回合的蛇不敢吃。

...

初步发现的这个结论，感觉很有用，于是写了个暴力，去把每条链生成出来，然后模拟一遍求出编号最小的“结束”回合。发现，在luogu过了55分（预期分数），牛客数据只过了20（n<=3)。

紧接着构造了一个反例：

链1：3-8 链2：4-5

发现，3-8之间，存在一条别的链4-5，那么，4-5之间必定有一条蛇要强行结束游戏，所以3其实是可以无脑吃的，也就是说：不能有边和边相交的情况。思考了一下后，在模拟的过程维护上一个链的端点即可。

修了这个锅以后，在luogu和牛客都过了55，证明结论大部分情况下对了（实际上感觉还有锅，等被hack再说吧）。

接下来改log速度的模拟大家都会，就不提了。

然后就考虑如何AC。

我并不擅长证明单调性之类的，于是考虑到这样一个事情：每次做决策后的蛇，在大多数情况下，比之前做过决策的蛇要短。

那么，维护两个队列，一个队列就是原始的蛇，一个队列是做过决策以后的蛇，每次做完决策以后，把新的长度用插入排序的方式从后面一步步换到前面去，直觉上看这个过程约等于O(1)的。

于是，在这次修改之后，终于通过了牛客和luogu的所有数据。

值得一提的是，luogu的数据貌似对这个做法强度不太够，不考虑链相交的情况，同时不进行插排的过程，无脑把新的蛇丢到队列末尾，也还是能AC。

代码因为是一步步改出来的，所以非常丑，见谅。

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int a[maxn];
int T,n,k,x,y;

int b[maxn<<1],c[maxn<<1];
int idb[maxn<<1],idc[maxn<<1];
int ans[maxn],pre[maxn];
int link[maxn];
int head1,head2,tail1,tail2;
void out()
{
    cout<<"******"<<endl;
//    cout<<head1<<" "<<tail1<<" "<<head2<<" "<<tail2<<endl;
    for (int i=head1;i<=tail1;i++) cout<<b[i]<<"("<<idb[i]<<")"<<" "; cout<<endl;    
    for (int i=head2;i<=tail2;i++) cout<<c[i]<<"("<<idc[i]<<")"<<" "; cout<<endl;
}

void work()
{
    for (int i=1;i<=n;i++) pre[i]=link[i]=0;
    for (int i=1;i<=n;i++) b[n-i+1+maxn]=a[i],idb[n-i+1+maxn]=i;

    head1=1+maxn,tail1=n+maxn;
    head2=1+maxn,tail2=0+maxn;

    int shang=-1; 
    for (int turn=1;turn<n;turn++)
    {
//        out();
        int zd,zx;
        int zuida,zuixiao;
        int zd1,zd2,zx1,zx2;
        int zh1,zh2,xh1,xh2;
        if (head1<=tail1) zd1=b[head1],zx1=b[tail1],zh1=idb[head1],xh1=idb[tail1]; else zd1=-1,zx1=999999999;
        if (head2<=tail2) zd2=c[head2],zx2=c[tail2],zh2=idc[head2],xh2=idc[tail2]; else zd2=-1,zx2=999999999;
        //拿出来最大的 
        if (zd2>zd1 || (zd2==zd1 && zh2>zh1))
        {
            zd=idc[head2];
            zuida=zd2;
            head2++;
        }
        else
        {
            zd=idb[head1];
            zuida=zd1;
            head1++;
        }
        //拿出来最小的
        if (zx2<zx1 || (zx2==zx1 && xh2<xh1))
        {
            zx=idc[tail2];
            zuixiao=zx2;
            tail2--;
        } 
        else
        {
            zx=idb[tail1];
            zuixiao=zx1;
            tail1--;
        }    

        if (pre[zx]!=0)
        {
            if (shang==-1 || shang==pre[zx]) 
            {
                link[turn]=pre[zx];
            }
            else
                break;
            shang=turn;
        }
        //最大的人这回合杀人了 
        pre[zd]=turn;
        //减去血量 
        int tt=zuida-zuixiao;
        int id=zd;

        tail2++; c[tail2]=tt; idc[tail2]=zd;
        int now=tail2;
        while (now>head2)
        {
            if (c[now]<c[now-1] || (c[now]==c[now-1] && idc[now]<idc[now-1])) break;
            swap(c[now],c[now-1]);
            swap(idc[now],idc[now-1]);
            now--;
        }
    }

    int zuixiao=n;
    for (int i=n;i>=1;i--)
    if (link[i])
    {
        int now=i,flag=0;
        while (now!=0)
        {
            if (flag==1) zuixiao=min(zuixiao,now);
            int pp=now;
            now=link[now];
            link[pp]=0;
            flag=1-flag;
        }
    }
    cout<<n-zuixiao+1<<endl;
    return;
}


int main()
{
    scanf("%d",&T);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    work();
    T--;
    while (T--)
    {
        scanf("%d",&k);
        while (k--)
        {
            scanf("%d%d",&x,&y);
            a[x]=y;
        }
        work();
    }
}