题目描述

你好，我是star_xiao ，我要开始诈骗了。
下面我会给出一个长度为 n 的数组 a，你需要判断是否存在一对下标 (i, j)（满足 1 ≤ i ≤ j ≤ n），使得以下条件成立：

max(a_i, a_i+1, …, a_j−1, a_j) ≥ a_i + a_i+1 + … + a_j−1 + a_j

输入格式

• 第一行：一个正整数 t（1 ≤ t ≤ 10⁵），表示测试用例数量。
• 对于每个测试用例：
  • 第一行：一个正整数 n（1 ≤ n ≤ 5×10⁵），表示数组长度。
  • 第二行：n 个整数 a_i（−10⁹ ≤ a_i ≤ 10⁹），表示数组第 i 个元素的值。
• 保证所有测试用例的 n 之和满足 ∑n ≤ 5×10⁵。

输出格式

• 每个测试用例占一行：
  • 如果存在满足条件的 (i, j)，输出 YES。
  • 否则，输出 NO。

说明/提示

• 对于第 1 个测试用例，(1, 5) 满足条件，因为 max(−1, 2, −3, 2, −1) > −1 + 2 − 3 + 2 − 1。
• 对于第 2 个测试用例，(2, 3) 满足条件，因为 max(3, −1) > 3 − 1。

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

YES
YES

Limitation

1s, 1024KiB for each test case.