我们要想到吃的过程应该是唯一确定的，而不是枚举出来的。

y ................................ x

性质1：一条蛇吃完最弱的蛇后，如果不会变成最弱的蛇，那么它一定不会死，所以它必然会吃。

证明： 情况1：x吃完y后，仍然最强，x必然可以吃y

情况2：x吃完y后，不是最强的，x必然可以吃y

性质2：分类讨论，一条蛇吃完最弱的蛇后，自己变得最弱。

此时，吃不吃取决于下条最强的蛇。

y y1 ................. x1 x

x y1 y2...............x2 x1

如果x1 能吃x, 那么，x就会选择不吃，让自己不成为最弱的 吃的情况：满足性质1，性质2通过讨论之后发现能吃

如果x1 不吃x，那么，x就会选择吃，多吃一个是一个

不吃的情况：吃了自己就要死，性质2通过讨论之后发现不能吃

递归实现性质2：

判断下一条最强的蛇是否会吃最弱的蛇。

f(cnt): 表示剩余cnt条蛇时，最强的蛇是否会吃最弱的蛇。

if cnt == 1: 不吃

if cnt == 2: 吃

if 最强的蛇吃完最弱的蛇后，满足性质1，则会吃

if 最强的蛇吃完最弱的蛇后，会变成最弱的蛇（满足性质2）：

	if f(cnt - 1) == true,则选择不吃
  
	else 吃

最后的问题是，如何线性的模拟整个决斗的过程。

两个队列维护

1.原数组从小到大是有序的

2.吃完之后的数组从大到小有序的

类似于归并的合并的两个数组去找最强和最弱的蛇即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 20, INF = 2e9;
int n;
int w[N];

struct Snake {
	int v, id; //实力和编号
	bool operator > (const Snake& T) const { //这样就可以直接比较了
		if(v != T.v) return v > T.v;
		return id > T.id;
	}
	
	bool operator == (const Snake& T) const {
		return v == T.v && id == T.id;
	}
}q1[N], q2[N];

int hh1, hh2, tt1, tt2;

Snake get_max() //从两个队列中取出，并删除最大值
{
	Snake res = {-1, -1};
	if(hh1 <= tt1) res = q1[tt1]; //假设最大的是第一个队列的最大值
	if(hh2 <= tt2 && q2[tt2] > res) res = q2[tt2]; //用第二个队列更新最大值
	if(hh1 <= tt1 && res == q1[tt1]) tt1 --;//如果最大值是在第一个队列tt1--
	else tt2 --;//否则tt2--
	return res;
}

Snake get_min(bool del = true) {//从两个队列中取出，并删除最小值，参数为false，则只是找最小值
	Snake res = {INF, INF};
	if(hh1 <= tt1) res = q1[hh1];
	if(hh2 <= tt2 && res > q2[hh2]) res = q2[hh2];
	if(del){
		if(hh1 <= tt1 && res == q1[hh1]) hh1 ++;
		else hh2 ++;
	}
	return res;
}

bool check(int cnt) //判断当前最强的蛇是否会吃最弱的蛇
{
	if(cnt == 1) return false;
	if(cnt == 2) return true;
	Snake strong = get_max(), weak = get_min();
	strong.v -= weak.v;
	if(strong > get_min(false)) //满足性质1 
		return true;
	q2[ --hh2] = strong;
	return !check(cnt - 1); //下一条蛇吃，我就不吃，下一条蛇不吃，我就吃
}
int solve()
{
	hh1 = 0, tt1 = -1, hh2 = n, tt2 = n - 1;
	for(int i = 1; i <= n; i++)
		q1[++tt1] = {w[i], i};
	
	int res = n;
	for(int i = 0; i < n - 1; i++) {
		Snake strong = get_max(), weak = get_min(); 
		//拿到最强的蛇和最弱的蛇，并删除两条蛇
		strong.v -= weak.v;
		res --;
		q2[ --hh2] = strong; //倒着存进队列2
		if(strong == get_min(false)) break; //如果最强的蛇变成的最弱，就停止吃
	}
	//如果下一条最强的蛇会吃掉最弱的蛇，则返回一步
	if(check(res)) res ++;
	return res;
}

int main()
{
	int t;
	cin >> t;
	for(int cases = 1; cases <= t; cases ++)
	{
		if(cases == 1) {
			cin >> n;
			for(int i = 1; i <= n; i++)
				cin >> w[i];
		}
		else {
			int m;
			cin >> m;
			while(m --) {
				int x, y;
				cin >> x >> y;
				w[x] = y;
			}
		}
		cout << solve() << endl;
	}
	return 0;
}