解题思路

• 设总和为 $S=\sum_{i=1}^n a_i$。

• 需要判断是否存在“非整段”的连续子段，其和 $\ge S$。

• 关键结论：所有“非整段”的连续子段的最大子段和，等于

  • 在前 $n-1$ 个元素上的最大子段和，和
  • 在后 $n-1$ 个元素上的最大子段和 的最大值。即

题目内容

某片场需要给参演人员采购盒饭，负责后勤的小周来到食堂，食堂里一共有 $n$ 种不同的盒饭，种类标记为 $1,2,3,...,n$ ，每种盒饭都有一个美味度 $a_i$ 。$a_i$ 越大，表示盒饭越好吃，由于有些盒饭味道可能很奇怪，于是 $a_i$ 有可能小于等于 $0$ 。

小周不了解演员们的口味偏好，于是每种盒饭都买了一份。回片场的路上小周在想：能不能找到这样一对 $l,r$ 满足 $1≤l≤r≤n$ ，且不满足 $[l,r]=[1,n]$ (即全选)，使得将 $[l,r]$ 这个种类内的盒饭各要一份，其美味度之和大于等于每一种会饭都买一份的美味度之和?

输入描述

第一行一个正整数 $T$ ，表示有 $T$ 组数据。

对于每一组数据，第一行一个正整数 $n$ ; 第二行 $n$ 个数 $a_1,a_2,...,a_n$ 。

$3≤n≤5*10^4,-100≤a_i≤100,1≤T≤5$

输出描述

对于每一组数型，如果找得到这样的 $l,r$ ，输出 $Yes$ ; 否则，输出 $No$ 。

样例1

输入

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

输出

No
Yes

说明

第一组数据，无论 $l,r$ 如何选择都比全选的美味度之和要小;

第二组数据，可以选择 $[l,r]=[1,1]$ ，美味度之和为 $-5$ ，等于全部选择的美味度之和。

当然也可以选择 $[l,r]=[1,2]$ ，美味度之和为 $0$ ，大于全部选择的美味度之和。