게리맨더링

시간 제한1초메모리 제한1024 MB

요약

수열을 연속한 구간으로 나눌 때 합이 양수인 구간이 음수인 구간보다 많게 만들 수 있는지 판정한다.

문제

길이 $N$ 인 수열 $A\_1, A\_2, \cdots, A\_N$ 이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과하도록 할 수 있을까요?

첫 줄에 테스트케이스의 수 $T$ 가 주어집니다. $(1 \le T \le 10\\,000)$

각 테스트케이스의 첫 줄에 배열의 길이 $N$ 이 주어집니다. $(1 \le N \le 200\\,000)$

둘째 줄에 정수 $A\_1, A\_2, \cdots, A\_N$ 이 공백으로 구분되어 주어집니다. $(-10^9 \le A\_i \le 10^9)$

입력에서 주어진 $N$ 의 합은 $200\\,000$ 을 넘지 않습니다.

각 테스트케이스마다 한 줄에 하나씩, 구간의 합이 양수인 것의 개수가 음수인 것의 개수를 초과하도록 할 수 있다면 “YES”를, 아니면 “NO”를 출력하세요.

예제 1

입력

4
4
2 2 -100 -100
5
-2 3 -2 3 -2
6
-1 1 -1 1 -1 2
7
-3 1 -4 5 -9 2 -6

예상 출력

YES
YES
YES
NO