← 返回题目列表

Codeforces · 1691/D

D. 最大 GEQ 总和

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。要求您找出不等式 $$$$$$\max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$$$$$$ 对于所有索引对 $$$(i, j)$$$ 是否成立,其中 $$$1 \leq i \leq j \leq n$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组的大小。

每个测试用例的下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

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

输出

对于每个测试用例,如果给定数组满足条件,则在新行输出“YES”,否则输出“NO”。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

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

输出 #1

YES
YES
NO

注意

在测试用例 $$$1$$$ 和 $$$2$$$ 中,所有 $$$(i, j)$$$ 对都满足给定条件。

在测试用例 $$$3$$$ 中,$$$(1, 2)$$$ 对的条件不满足,因为 $$$\max(2, 3) < 2 + 3$$$。