You are given an array aa of nn integers. You are asked to find out if the inequality

max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+aj

holds for all pairs of indices (i,j)(i,j), where 1≤i≤j≤n1≤i≤j≤n.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1051≤t≤105). Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105)  — the size of the array.

The next line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower).

Example

input

3

4

-1 1 -1 2

5

-1 2 -3 2 -1

3

2 3 -1

output

YES

YES

NO

题意： 给出一个长度为n的数组，问该数组是否任意区间都满足区间最大值 >= 区间加和。

分析： 可以按照最大值来枚举区间，也就是遍历数组a，判断以a[i]为最大值的所有区间是否满足，而a[i]作为最大值的区间就是从i处找左右第一个大于a[i]的位置，这个过程可以用单调栈实现。找到区间了就该判断这些区间是否满足题意了，在单调栈找到的范围内最大值不变，永远都是a[i]，所以可以求一下区间和的最大值，因为区间和能够用前缀和差值来表示，区间和最大也就是最大的前缀和减最小的前缀和，不过这个区间和必须包含i这个位置，所以最大的前缀和要在[i, r[i]-1]中找，最小的前缀和要在[l[i], i-1]中找，因为是不带修改的区间最值查询，直接用st表会更方便。最后要注意用st表的时候f[0]也要进行更新，因为下面在求最小值的时候用到了f[0]的信息。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;int s[200005], a[200005], f1[200005][20], f2[200005][20], n;
int l[200005], r[200005], st[200005];void ST(){for(int i = 0; i <= n; i ++) f1[i][0] = s[i]; for(int j = 1; j < 20; j ++) for(int i = 0; i+(1<> T;while(T--){scanf("%lld", &n);for(int i = 1; i <= n; i++){scanf("%lld", &a[i]);s[i] = s[i-1]+a[i];l[i] = r[i] = 0;}ST();int top = 0; st[0] = 0;for(int i = 1; i <= n; i++){while(top > 0 && a[i] > a[st[top]]){r[st[top]] = i; top--; } st[++top] = i; } top = 0;st[0] = 0;for(int i = 1; i <= n; i++){while(top > 0 && a[i] >= a[st[top]])top--; l[i] = st[top];st[++top] = i; } for(int i = 1; i <= n; i++)if(!r[i]) r[i] = n+1;bool flag = false;for(int i = 1; i <= n; i++){int mx = _max(i, r[i]-1), mn = _min(l[i], i-1);if(mx-mn > a[i]){flag = true;break;}}if(flag) puts("No");else puts("Yes");}return 0;
}