RT，思路和第一篇题解差不多

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[1000006],k,x,y,lq1,lq2,i,p,ans,cnt,minn;
struct _{long long v,id;}tmp;
bool operator >(_ x,_ y){if(x.v==y.v)return x.id>y.id;return x.v>y.v;}
bool operator <(_ x,_ y){if(x.v==y.v)return x.id<y.id;return x.v<y.v;}
bool operator >=(_ x,_ y){if(x.v==y.v)return x.id>=y.id;return x.v>=y.v;}
_ operator -(_ x,_ y){return _{x.v-y.v,x.id};}
deque<_>q1,q2;
int main()
{
	freopen("P7078_9.in","r",stdin);
	cin>>t>>n;
	for(i = 1;i<=n;i++)cin>>a[i],q1.push_back({a[i],i});
	tmp = q1.front();
	q1.pop_front();
	if(q1.back()-tmp>=q1.front())
	{
		q2.push_front(q1.back()-tmp);
		q1.pop_back();
		while(q1.size())
		{
			tmp = q1.front();
			q1.pop_front();
			if(max(q1.back(),q2.back())-tmp<q1.front()){q1.push_front(tmp);break;}
			if(q1.back()>q2.back())q2.push_front(q1.back()-tmp),q1.pop_back();
			else q2.push_front(q2.back()-tmp),q2.pop_back();
		}
		ans = q1.size()+q2.size();
		while(q1.size())
		{
			tmp = q1.front();
			q1.pop_front();
			if(q2.empty())
			{
				if(q1.back()-tmp>=q1.front())break;
				q1.push_front(q1.back()-tmp),q1.pop_back();
			}
			else
			{
				if(max(q1.back(),q2.back())-tmp>=q1.front())break;
				if(q1.back()>q2.back())q1.push_front(q1.back()-tmp),q1.pop_back();
				else q1.push_front(q2.back()-tmp),q2.pop_back();
			}
			cnt++;
		}
		if(cnt!=0)
		{
			ans-=cnt;
			if(!(cnt&1))cnt--;
		}
		else if(!(ans&1))cnt--; 
		cout<<ans+cnt<<'\n';
	}
	else
	{
		q1.push_front(tmp);
		ans = q1.size()+q2.size();
		while(q1.size())
		{
			tmp = q1.front();
			q1.pop_front();
			if(q2.empty())
			{
				if(q1.back()-tmp>=q1.front())break;
				q1.push_front(q1.back()-tmp),q1.pop_back();
			}
			else
			{
				if(max(q1.back(),q2.back())-tmp<q1.front()){q1.push_front(tmp);break;}
				if(q1.back()>q2.back())q1.push_front(q1.back()-tmp),q1.pop_back();
				else q1.push_front(q2.back()-tmp),q2.pop_back();
			}
			cnt++;
		}
		if(cnt!=0)
		{
			ans-=cnt;
			if(!(cnt&1))cnt--;
		}
		else if(!(ans&1))cnt--;
		cout<<ans+cnt<<'\n';
	}
	t--;
	while(t--)
	{
		while(q1.size())q1.pop_back();
		while(q2.size())q2.pop_back();
		cnt = 0;ans = 0;
		cin>>k;
		for(i = 1;i<=k;i++)cin>>x>>y,a[x] = y;
		for(i = 1;i<=n;i++)q1.push_back({a[i],i});
		tmp = q1.front();
		q1.pop_front();
		if(q1.back()-tmp>=q1.front())
		{
			q2.push_front(q1.back()-tmp);
			q1.pop_back();
			while(q1.size())
			{
				tmp = q1.front();
				q1.pop_front();
				if(max(q1.back(),q2.back())-tmp<q1.front()){q1.push_front(tmp);break;}
				if(q1.back()>q2.back())q2.push_front(q1.back()-tmp),q1.pop_back();
				else q2.push_front(q2.back()-tmp),q2.pop_back();
			}
			ans = q1.size()+q2.size();
			while(q1.size())
			{
				tmp = q1.front();
				q1.pop_front();
				if(q2.empty())
				{
					if(q1.back()-tmp>=q1.front())break;
					q1.push_front(q1.back()-tmp),q1.pop_back();
				}
				else
				{
					if(max(q1.back(),q2.back())-tmp>=q1.front())break;
					if(q1.back()>q2.back())q1.push_front(q1.back()-tmp),q1.pop_back();
					else q1.push_front(q2.back()-tmp),q2.pop_back();
				}
				cnt++;
			}
			if(cnt!=0)
			{
				ans-=cnt;
				if(!(cnt&1))cnt--;
			}
			else if(!(ans&1))cnt--;
			cout<<ans+cnt<<'\n';
		}
		else
		{
			q1.push_front(tmp);
			ans = q1.size()+q2.size();
			while(q1.size())
			{
				tmp = q1.front();
				q1.pop_front();
				if(q2.empty())
				{
					if(q1.back()-tmp>=q1.front())break;
					q1.push_front(q1.back()-tmp),q1.pop_back();
				}
				else
				{
					if(max(q1.back(),q2.back())-tmp>=q1.front())break;
					if(q1.back()>q2.back())q1.push_front(q1.back()-tmp),q1.pop_back();
					else q1.push_front(q2.back()-tmp),q2.pop_back();
				}
				cnt++;
			}
			if(cnt!=0)
			{
				ans-=cnt;
				if(!(cnt&1))cnt--;
			}
			else if(!(ans&1))cnt--;
			cout<<ans+cnt<<'\n';
		}
	}
}