该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

wcqk 觉得《上帝造题的七分钟 · 神奇的游戏1》还不够神经，于是便有了本题。

• 第一分钟，风说，要有数组，于是便有了一串长度为 $n$ 的整数序列。
• 第二分钟，旷什么都没有发生。
• 第三分钟，星什么都没有发生。
• 第四分钟，栖说，要提高难度，于是便有了难度的评级。
• 第五分钟，四说，要有约束，于是便有了时间限制与内存限制。
• 第六分钟，vivo50 ，什么都没有发生。
• 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。

所以这个神圣的任务就交给你了。

题目描述

一个长度为 $n$ 的数组 $a$。你需要判断是否存在一对下标 $(i, j)$，满足 $1 \le i \le j \le n$，使得以下式子成立：

其中 $\max$ 表示区间内的最大值，$\sum$ 表示区间内所有元素的和。

输入格式

第一行输入一个正整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个正整数 $n$（$1 \le n \le10^5$），表示数组的长度。
• 第二行输入 $n$ 个整数 $a_i$（$-10^9 \le a_i \le 10^9$），表示数组中的元素。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行：

• 如果存在满足条件的 $(i, j)$，输出 YES；
• 否则输出 NO。

输入输出样例 #1

输入 #1

3  
3  
-1 5 -1  
4  
1 2 3 4  
4  
-2 -5 10 -2  

输出 #1

YES  
NO  
YES  

说明/提示

第一个测试用例：$n = 3$，$a = [-1, 5, -1]$

取区间 $[1, 3]$，最大值 $\max = 5$，总和 $(-1) + 5 + (-1) = 3$，满足 $5 > 3$，因此输出 YES。

第二个测试用例：$n = 4$，$a = [1, 2, 3, 4]$

所有元素均为正数，对于任意区间，总和 $\ge$ 最大值 $+$ 至少一个正数 $>$ 最大值，因此不存在满足条件的区间，输出 NO。

第三个测试用例：$n = 4$，$a = [-2, -5, 10, -2]$

取区间 $[2, 4]$，最大值 $\max = 10$，总和 $(-5) + 10 + (-2) = 3$，满足 $10 > 3$，因此输出 YES。

数据范围与约定

• $1 \le t \le 10^5$
• $1 \le n \le 10^5$
• $-10^9 \le a_i \le 10^9$
• $\sum n \le 5 \times 10^5$