$ \def\myred#1{{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $ $\def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}}$

You are given a sequence of $n$ non-negative integers $a_1, a_2, \ldots, a_n$. Initially, all the elements of the sequence are unpainted. You can paint each number $\RED$ or $\BLUE$ (but not both), or leave it unpainted.

For a color $c$, $\text{Count}(c)$ is the number of elements in the sequence painted with that color and $\text{Sum}(c)$ is the sum of the elements in the sequence painted with that color.

For example, if the given sequence is $[2, 8, 6, 3, 1]$ and it is painted this way: $[\myblue{2}, 8, \myred{6}, \myblue{3}, 1]$ (where $6$ is painted red, $2$ and $3$ are painted blue, $1$ and $8$ are unpainted) then $\text{Sum}(\RED)=6$, $\text{Sum}(\BLUE)=2+3=5$, $\text{Count}(\RED)=1$, and $\text{Count}(\BLUE)=2$.

Determine if it is possible to paint the sequence so that $\text{Sum}(\RED) > \text{Sum}(\BLUE)$ and $\text{Count}(\RED) < \text{Count}(\BLUE)$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($3\le n\le 2\cdot 10^5$) — the length of the given sequence.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 10^9$) — the given sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.


-----Output-----

For each test case, print YES if it is possible to paint the given sequence satisfying the above requirements, and NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).


-----Examples-----

Input
4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
Output
NO
YES
NO
NO


-----Note-----

In the first test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $[\myblue{1},\myblue{2},\myred{3}]$ (where $3$ is painted red, $1$ and $2$ are painted blue) then $\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$, but $\text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3$. So, this is not a possible way to paint the sequence.

In the second test case, a possible way to paint the sequence is described in the statement. We can see that $\text{Sum}(\RED)=6 > \text{Sum}(\BLUE)=5$ and $\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$.

In the third test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $[\myred{3},\myred{5},\myblue{4}, \myblue{2}]$ (where $3$ and $5$ are painted red, $4$ and $2$ are painted blue) then $\text{Sum}(\RED) = 8 > \text{Sum}(\BLUE) = 6$ but $\text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2$. So, this is not a possible way to paint the sequence.

In the fourth test case, it can be proven that there is no possible way to paint the sequence satisfying sum and count constraints.

Source: codeforces | Difficulty: EASY
Tags: Constructive algorithms

Sorting

Amortized analysis

Greedy algorithms

Complete search


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split(' ')))
	if sum(a[:(n + 1) // 2]) < sum(a[-((n - 1) // 2):]):
		print('YES')
	else:
		print('NO')


test = int(input())
for i in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	mid = (n + 1) // 2
	if sum(a[:mid]) < sum(a[:-mid:-1]):
		print('YES')
	else:
		print('NO')


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	up = math.ceil(n / 2)
	if n % 2 == 0 and sum(a[0:up]) < sum(a[up + 1:]) or (n % 2 == 1 and sum(a[0:up]) < sum(a[up:])):
		print('YES')
	else:
		print('NO')


import sys
import heapq
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tests = inp()
for wx in range(tests):
	n = inp()
	lis = inlt()
	lis.sort()
	count1 = n // 2 + 1
	count2 = len(lis) - count1
	sum1 = sum(lis[:count1])
	sum2 = sum(lis[count1:])
	i = count1 - 1
	possible = False
	while count1 > count2:
		if sum1 < sum2:
			possible = True
			break
		sum1 -= lis[i]
		i -= 1
		count1 -= 1
	if possible:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	e = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a = a[::-1]
	if e % 2 == 1:
		if sum(a[:e // 2]) > sum(a[e // 2:]):
			print('YES')
		else:
			print('NO')
	elif sum(a[:e // 2 - 1]) > sum(a[e // 2:]):
		print('YES')
	else:
		print('NO')


def is_possible(n, arr):
	half = (n + 1) // 2
	if sum(arr[:half]) < sum(arr[-half + 1:]):
		return 'YES'
	return 'NO'
flags = []
for _ in range(int(input())):
	(n, arr) = (int(input()), list(map(int, input().split())))
	arr.sort()
	print(is_possible(n, arr))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	if n % 2 != 0:
		if sum(l[:n // 2]) > sum(l[n // 2:]):
			print('YES')
		else:
			print('NO')
	else:
		a = sum(l[:n // 2 - 1])
		b = sum(l[n // 2 - 1:])
		if a > b:
			print('YES')
		elif a > b - l[n // 2 - 1]:
			print('YES')
		else:
			print('NO')


ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mx = 10 ** 5
inp = lambda : int(input())
for i in range(inp()):
	n = inp()
	arr = ints()
	arr.sort()
	sum1 = sum(arr[:n // 2 + 1]) if n % 2 else sum(arr[:n // 2])
	sum2 = sum(arr[n // 2 + 1:])
	print('YES' if sum2 > sum1 else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(st, end) = ((n - 1) // 2, n // 2 + 1)
	if sum(a[:st + 1]) < sum(a[end:]):
		print('YES')
	else:
		print('NO')


t = int(input())
result = []
for case in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	seq.sort()
	if n % 2:
		part1 = seq[:n // 2 + 1]
		part2 = seq[-(n - n // 2 - 1):]
	else:
		part1 = seq[:n // 2]
		part2 = seq[-(n - n // 2 - 1):]
	if sum(part1) < sum(part2):
		result.append('YES')
	else:
		result.append('NO')
for x in result:
	print(x)


for tc in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	if n % 2 == 1:
		sum1 = sum(arr[0:n // 2 + 1])
		sum2 = sum(arr[n // 2 + 1:n])
		if sum2 > sum1:
			print('YES')
		else:
			print('NO')
	else:
		sum1 = sum(arr[0:n // 2])
		sum2 = sum(arr[n // 2 + 1:n])
		if sum2 > sum1:
			print('YES')
		else:
			print('NO')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def func():
	n = inp()
	l = seq()
	l.sort()
	mid = n // 2 + 1
	if sum(l[:mid]) < sum(l[mid:]):
		print('YES')
	elif not n % 2 and sum(l[:mid - 1]) < sum(l[mid:]):
		print('YES')
	else:
		print('NO')
t = inp()
for i in range(t):
	func()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	he_n = n // 2
	if n & 1:
		s_pre = sum(a[:he_n + 1])
		s_a = sum(a[he_n + 1:])
	else:
		s_pre = sum(a[:he_n])
		s_a = sum(a[he_n + 1:])
	print('YNEOS'[s_a <= s_pre::2])


def find_possible():
	number_examples = int(input())
	for test_case in range(number_examples):
		input()
		test_case = list(map(int, input().split()))
		test_case.sort()
		possible = 'NO'
		big_quantity = -1
		small_quantity = 1
		small_sum = sum(test_case[:2])
		big_sum = test_case[big_quantity]
		for i in range(len(test_case) // 2):
			if small_sum < big_sum:
				possible = 'YES'
				break
			big_quantity -= 1
			small_quantity += 1
			small_sum += test_case[small_quantity]
			big_sum += test_case[big_quantity]
		print(possible)
find_possible()


t = int(input())
for veces in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	if n % 2 == 1:
		m = n // 2 + 1
		a = sum(L[0:m])
		b = sum(L[m:n])
	else:
		m = n // 2
		a = sum(L[0:m])
		b = sum(L[m + 1:n])
	if a < b:
		print('YES')
	else:
		print('NO')


inp = int(input())
for _ in range(inp):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(s1, s2) = (a[0], 0)
	for i in range(1, (n + 1) // 2 + 1):
		s1 += a[i]
		s2 += a[n - i]
		if s1 < s2:
			print('YES')
			break
	else:
		print('NO')


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().strip().split()))
	l.sort()
	r = (n - 1) // 2
	m1 = sum(l[n - r:])
	m2 = sum(l[:r + 1])
	if m1 > m2:
		sys.stdout.write('YES' + '\n')
	else:
		sys.stdout.write('NO' + '\n')


cases = int(input())
sol = []
while cases > 0:
	len = int(input())
	numbers = [int(num) for num in input().split()]
	numbers.sort()
	red = sum(numbers[int(len / 2 + (1 if len % 2 == 0 else 0.5))::1])
	blue = sum(numbers[0:int(len / 2 + (0 if len % 2 == 0 else 0.5)):1])
	sol.append('YES' if red > blue else 'NO')
	cases -= 1
for s in sol:
	print(s)


tc = int(input())
for i in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(x, y) = (a[0], 0)
	for i in range(1, n // 2 + n % 2):
		x += a[i]
		y += a[-i]
		if x < y:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	if n % 2 == 0:
		s = sum(a[:n // 2])
		a.pop(n // 2)
	else:
		s = sum(a[:n // 2 + 1])
	if 2 * s < sum(a):
		print('YES')
	else:
		print('NO')


from sys import stdin
input = stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		nums = list(map(int, input().split()))
		nums.sort()
		r_sum = nums[n - 1]
		b_sum = nums[0] + nums[1]
		st = 2
		en = n - 2
		flag = 0
		if r_sum > b_sum:
			flag = 1
		while st < en:
			r_sum += nums[en]
			b_sum += nums[st]
			st += 1
			en -= 1
			if r_sum > b_sum:
				flag = 1
				break
		print('YES' if flag == 1 else 'NO')
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	(a, b) = (l[0], 0)
	for i in range(1, n // 2 + n % 2):
		a += l[i]
		b += l[n - i]
		if a < b:
			print('YES')
			break
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n % 2 == 1:
		k = (n + 1) // 2
		if sum(a[:k]) < sum(a[k:]):
			print('YES')
		else:
			print('NO')
	else:
		k = (n + 2) // 2
		if sum(a[:k - 1]) < sum(a[k:]):
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	a.sort()
	(r1, l2) = ((n - 1) // 2, (n + 2) // 2)
	(b, r) = (sum(a[:r1 + 1]), sum(a[l2:]))
	print('YES' if r > b else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()), reverse=True)
	h = (n + 1) // 2
	p = n % 2
	print('YES' if sum(a[:h - 1]) > sum(a[h - p:]) else 'NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if n % 2 == 0:
		if sum(l[:n // 2]) < sum(l[n // 2 + 1:]):
			print('YES')
		else:
			print('NO')
	elif sum(l[:n // 2 + 1]) < sum(l[n // 2 + 1:]):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	seq = [int(i) for i in input().split()]
	seq.sort()
	blue_sum = sum(seq[:(n - 1) // 2 + 1])
	red_sum = sum(seq[n // 2 + 1:])
	print('YES' if red_sum > blue_sum else 'NO')


num = int(input())
for _ in range(num):
	n = int(input())
	seq1 = [int(i) for i in input().split()]
	seq1.sort()
	blue_sum = sum(seq1[:(n - 1) // 2 + 1])
	red_sum = sum(seq1[n // 2 + 1:])
	print('YES' if red_sum > blue_sum else 'NO')


def solve():
	n = int(input())
	seq = sorted([int(x) for x in input().split()])
	if sum(seq[:n // 2 + (1 if n % 2 == 1 else 0)]) < sum(seq[n // 2 + 1:]):
		print('YES')
	else:
		print('NO')
for tc in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if n % 2 == 0:
		if sum(arr[:n // 2]) < sum(arr[n // 2 + 1:]):
			print('YES')
		else:
			print('NO')
	elif sum(arr[:n // 2 + 1]) < sum(arr[n // 2 + 1:]):
		print('YES')
	else:
		print('NO')


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def yes(t):
	if t:
		return 'YES'
	return 'NO'

def printjoin(l):
	l = [str(i) for i in l]
	return ' '.join(l)

def solve():
	n = int(input())
	s = intlist()
	s = sorted(s, reverse=True)
	if n % 2 == 1:
		to = n // 2
	else:
		to = n // 2 - 1
	a = 0
	b = s[-1]
	for i in range(to):
		a += s[i]
		b += s[-2 - i]
		if a > b:
			return 'YES'
	return 'NO'
t = input()
for tt in range(int(t)):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	if n % 2 == 0:
		if sum(a[0:n // 2]) < sum(a[n // 2 + 1:]):
			print('YES')
		else:
			print('NO')
	elif sum(a[0:n // 2 + 1]) < sum(a[n // 2 + 1:]):
		print('YES')
	else:
		print('NO')


try:
	for _ in range(0, int(input())):
		n = int(input())
		mylist = list(map(int, input().split()))
		mylist.sort()
		if n % 2 == 0:
			Sblue = sum(mylist[:n // 2])
			Sred = sum(mylist[n // 2 + 1:])
			if Sred > Sblue:
				print('YES')
				continue
			else:
				print('NO')
				continue
		else:
			Sblue = sum(mylist[:n // 2 + 1])
			Sred = sum(mylist[n // 2 + 1:])
			if Sred > Sblue:
				print('YES')
				continue
			else:
				print('NO')
				continue
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	a1 = a[0]
	a2 = 0
	flag = False
	for i in range(1, n // 2 + 1):
		a1 += a[i]
		a2 += a[-i]
		if a1 < a2:
			flag = True
			break
	print('YES') if flag else print('NO')


import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
	t = int(input())
	for _ in range(t):
		a = int(input())
		s = list(map(int, input().split()))
		s = sorted(s)
		sum1 = s[0]
		sum2 = 0
		f = False
		if a % 2 != 0:
			for i in range(1, a // 2 + 1):
				sum1 += s[i]
				sum2 += s[-i]
				if sum2 > sum1:
					print(f'YES\n')
					f = True
					break
			if f == False:
				print(f'NO\n')
		else:
			for i in range(1, a // 2):
				sum1 += s[i]
				sum2 += s[-i]
				if sum2 > sum1:
					print(f'YES\n')
					f = True
					break
			if f == False:
				print(f'NO\n')
main()


import sys

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		nums = list(map(int, sys.stdin.readline().split()))
		nums.sort()
		sum_blue = nums[0] + nums[1]
		left = 1
		count_blue = 2
		sum_red = nums[-1]
		count_red = 1
		right = n - 1
		while left < right:
			if sum_red > sum_blue and count_blue > count_red:
				break
			elif sum_red <= sum_blue and count_blue > count_red:
				if left + 1 == right:
					break
				else:
					right -= 1
					left += 1
					sum_red += nums[right]
					sum_blue += nums[left]
		if sum_red > sum_blue and count_blue > count_red:
			print('YES')
		else:
			print('NO')
main()


def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		(l, r) = (1, n - 1)
		(sum_l, sum_r) = (arr[0], 0)
		flag = False
		while l < r:
			sum_l += arr[l]
			sum_r += arr[r]
			if sum_l < sum_r:
				flag = True
				break
			l += 1
			r -= 1
		print('YES' if flag else 'NO')
main()


t = int(input())

def solve(n, ar):
	ar.sort()
	(smb, smr, cb, cr) = (ar[0], 0, 1, 0)
	(l, r) = (0, n)
	while l < r:
		if smb < smr:
			return 'YES'
		l += 1
		r -= 1
		if l != r:
			smb += ar[l]
			smr += ar[r]
	return 'NO'
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(solve(n, ar))


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	(sb, sr, cr, cb, f) = (l[n - 1], 0, 0, n - 2, 0)
	while cr < cb:
		sr += l[cr]
		sb += l[cb]
		if sr > sb:
			f = 1
			break
		else:
			cr += 1
			cb -= 1
	if f:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	l = int(input())
	n = list(map(int, input().split()))
	sorted_n = sorted(n)
	ans = ''
	mid = l // 2
	if l % 2 != 0:
		mid = mid + 1
	mid = mid
	lenBmid = len(sorted_n[:mid])
	lenAmid = len(sorted_n[mid:])
	if lenBmid == lenAmid:
		Blue_Sum = sum(sorted_n[:mid])
		Red_Sum = sum(sorted_n[mid:][1:])
		if Red_Sum > Blue_Sum:
			ans = 'YES'
		else:
			ans = 'NO'
	elif lenBmid > lenAmid:
		Blue_Sum = sum(sorted_n[:mid])
		Red_Sum = sum(sorted_n[mid:])
		if Red_Sum > Blue_Sum:
			ans = 'YES'
		else:
			ans = 'NO'
	print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	sum1 = 0
	sum2 = a[0]
	i = 1
	j = n - 1
	while i < j:
		sum1 += a[j]
		sum2 += a[i]
		i += 1
		j -= 1
		if sum1 > sum2:
			print(yes)
			return
	print(no)
yes = 'YES'
no = 'NO'
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	li = sorted(list(map(int, input().split())))
	print('YES' if len(li) % 2 and sum(li[len(li) // 2 + 1:]) > sum(li[:len(li) // 2 + 1]) and (len(li[len(li) // 2 + 1:]) < len(li[:len(li) // 2 + 1])) or (not len(li) % 2 and sum(li[len(li) // 2 + 1:]) > sum(li[:len(li) // 2]) and (len(li[len(li) // 2 + 1:]) < len(li[:len(li) // 2]))) or (len(li) % 2 and sum(li[len(li) // 2 + 2:]) > sum(li[:len(li) // 2 + 1]) and (len(li[len(li) // 2 + 2:]) < len(li[:len(li) // 2 + 1]))) else 'NO')


def sol(S):
	(suml, sumr) = (S[0], 0)
	for i in range(1, len(S) // 2, 1):
		suml += S[i]
		sumr += S[-i]
		if suml < sumr:
			return 'YES'
	suml += S[len(S) // 2]
	if len(S) % 2 == 1:
		sumr += S[-len(S) // 2 + 1]
	if suml < sumr:
		return 'YES'
	return 'NO'
N = input()
A = []
for i in range(int(N)):
	n = int(input())
	S = [int(s) for s in input().split(' ')]
	A.append(sol(sorted(S)))
for a in A:
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	num.sort()
	ok = False
	blue = num[0]
	red = 0
	i = 1
	j = n - 1
	while i < j:
		blue += num[i]
		red += num[j]
		if blue < red:
			ok = True
			break
		i += 1
		j -= 1
	if ok:
		print('YES')
	else:
		print('NO')


t = int(input())

def fun(n, s):
	s.sort()
	if n % 2 == 1:
		a = sum(s[0:n // 2 + 1])
		b = sum(s) - a
	else:
		a = sum(s[0:n // 2])
		b = sum(s[n // 2 + 1:n])
	return (a, b)
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	(x, y) = fun(n, s)
	if y > x:
		print('YES')
	else:
		print('NO')


n = int(input())

def check(seq):
	seq.sort()
	i = 1
	j = len(seq) - 1
	sum_red = seq[j]
	sum_blue = seq[0] + seq[1]
	while i < j:
		if sum_red > sum_blue:
			return 'YES'
		else:
			j -= 1
			i += 1
			sum_red += seq[j]
			sum_blue += seq[i]
	return 'NO'
for i in range(n):
	m = int(input())
	seq = list(map(int, input().split()))
	print(check(seq))


from math import ceil

def posible(l, n):
	c = ceil(n / 2) - 1
	r = sum(l[-c:])
	for i in range(c + 1, n - c + 1):
		b = sum(l[0:i])
		if r > b or l[-1] > b:
			return 'YES'
	return 'NO'
x = int(input())
for z in range(x):
	n = int(input())
	l = [int(i) for i in input().split()]
	if n < 3:
		print('NO')
	else:
		l.sort()
		print(posible(l, n))


TESTCASE = int(input())

def coloring(data: list):
	data = sorted(data, reverse=True)
	L = len(data)
	left = (L - 1) // 2
	right = L - left - 1
	if sum(data[:left]) > sum(data[right:]):
		return 'YES'
	return 'NO'
for _ in range(TESTCASE):
	input()
	element = input().strip()
	Data = list(map(lambda x: int(x), element.split(' ')))
	print(coloring(Data))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	count = 0
	if n % 2 == 0:
		r = l[:int(n / 2) - 1]
		b = l[int(n / 2) - 1:]
		b.pop(0)
	else:
		r = l[:int((n + 1) / 2) - 1]
		b = l[int((n + 1) / 2) - 1:]
	if sum(r) > sum(b):
		print('YES')
	else:
		print('NO')


import math
t = int(input())

def f(arr):
	if n < 2:
		return 'YES'
	(left, right) = (arr[0] + arr[1], arr[-1])
	for i in range(2, n // 2 + 1):
		if right > left:
			return 'YES'
		(left, right) = (left + arr[i], right + arr[-i])
	return 'YES' if right > left else 'NO'
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(f(a))


t = int(input())
for i in range(t):
	n = int(input())
	sequences = list(map(int, input().split()))
	sequences.sort()
	red_tot = 0
	blue_tot = sequences[0]
	for j in range(1, n // 2 + 1):
		blue_tot += sequences[j]
		red_tot += sequences[-j]
		if red_tot > blue_tot:
			print('YES')
			break
	if red_tot <= blue_tot:
		print('NO')


import math
testCases = int(input())
for _ in range(testCases):
	tamSequence = int(input())
	sequence = list(map(int, input().split()))
	divSequence = int(math.ceil(tamSequence / 2))
	seqSorted = sorted(sequence, reverse=True)
	sumBlue = sum(seqSorted[-divSequence:])
	sumRed = sum(seqSorted[:divSequence - 1])
	if sumRed > sumBlue:
		print('YES')
	else:
		print('NO')


def solve():
	length = int(input())
	numbers = list(map(int, input().split()))
	numbers.sort()
	counter = 1
	redSum = 0
	blueSum = numbers[0]
	while counter <= length // 2:
		redSum += numbers[length - counter]
		blueSum += numbers[counter]
		if redSum > blueSum:
			print('YES')
			return
		counter += 1
	print('NO')
tests = int(input())
while tests > 0:
	tests -= 1
	solve()


def solution():
	t = int(input())
	for _ in range(t):
		n = int(input())
		nums = list(map(int, input().split()))
		nums.sort()
		(B, R) = (nums[0] + nums[1], nums[-1])
		for i in range(2, len(nums) // 2 + 1):
			(B, R) = (B + nums[i], R + nums[-i])
			if B < R:
				break
		if B < R:
			print('YES')
		else:
			print('NO')
solution()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if n % 2 == 0:
		k = n // 2
		if sum(arr[:k + 1]) < sum(arr[k:]):
			print('YES')
		else:
			print('NO')
	else:
		k = n // 2 + 1
		if sum(arr[:k]) < sum(arr[k:]):
			print('YES')
		else:
			print('NO')


def main(lst):
	small = lst[0] + lst[1]
	s = 1
	large = lst[-1]
	l = len(lst) - 1
	while s < l:
		if small < large:
			return 'YES'
		s += 1
		small += lst[s]
		l -= 1
		large += lst[l]
	return 'NO'
no = int(input())
for i in range(no):
	n = input()
	lstt = input().split()
	lstt = [int(num) for num in lstt]
	lstt.sort()
	print(main(lstt))


def solve(length, llist):
	llist.sort()
	(l, r) = (1, length - 1)
	large_sum = llist[0]
	small_sum = 0
	while l < r:
		large_sum += llist[l]
		small_sum += llist[r]
		l += 1
		r -= 1
		if small_sum > large_sum:
			print('YES')
			return
	print('NO')
t = int(input())
for _ in range(t):
	length = int(input())
	inputta = input().split()
	llist = list(map(int, inputta))
	solve(length, llist)


n = int(input())

def quality(n):
	for i in range(n):
		m = int(input())
		if m < 3:
			print('NO')
			continue
		arr = list(map(int, input().split()))
		arr.sort()
		(left, right) = (1, m - 1)
		(sumR, sumG) = (arr[0], 0)
		while left < right:
			sumG += arr[right]
			right -= 1
			sumR += arr[left]
			left += 1
			if sumG > sumR:
				break
		if sumG > sumR:
			print('YES')
		else:
			print('NO')
quality(n)


def YES():
	print('YES')

def NO():
	print('NO')
TT = int(input())
while TT:
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	fl = n % 2
	l = n // 2 + fl
	if sum(a[:l]) < sum(a[l + 1 - fl:]):
		YES()
	else:
		NO()
	TT -= 1


b = int(input())
for _ in range(b):
	m = int(input())
	seq2 = [int(i) for i in input().split()]
	seq2.sort()
	blue_sum = sum(seq2[:(m - 1) // 2 + 1])
	red_sum = sum(seq2[m // 2 + 1:])
	print('YES' if red_sum > blue_sum else 'NO')


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	a.sort(reverse=True)
	r = 0
	j = len(a) - 1
	b = a[j]
	j -= 1
	for i in range(n):
		r += a[i]
		if i < j:
			b += a[j]
			j -= 1
		else:
			break
		if r > b:
			print('YES')
			return
	print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from collections import *
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	flag = 0
	sum = l[0] + l[1]
	count = l[n - 1]
	i = 1
	j = n - 1
	while i < j:
		if count > sum:
			flag = 1
			break
		else:
			i += 1
			j -= 1
			sum += l[i]
			count += l[j]
	if flag:
		print('YES')
	else:
		print('NO')


def main():
	input()
	a = sorted(list(map(int, input().split())))
	countB = 0
	countR = 0
	sumB = 0
	sumR = 0
	l = 0
	r = len(a) - 1
	for i in range(len(a) + 1):
		if sumR <= sumB:
			countR += 1
			sumR += a[r]
			r -= 1
		elif countR >= countB:
			countB += 1
			sumB += a[l]
			l += 1
		else:
			return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	print(main())


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	if n & 1:
		if sum(a[:(n >> 1) + 1]) >= sum(a[n // 2 + 1:]):
			print('NO')
		else:
			print('YES')
	elif sum(a[:n >> 1]) >= sum(a[n // 2 + 1:]):
		print('NO')
	else:
		print('YES')


t = int(input())

def checksum(r):
	sum_r = r[-1]
	index_r = n - 1
	sum_b = r[0] + r[1]
	index_b = 1
	while index_b < index_r:
		if sum_r > sum_b:
			print('YES')
			return
		else:
			index_b += 1
			sum_b += r[index_b]
			index_r -= 1
			sum_r += r[index_r]
	print('NO')
for i in range(t):
	n = int(input())
	r = list(map(int, input().rstrip().split()))
	r = sorted(r)
	checksum(r)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	if n % 2 == 1 and sum(l[:n // 2]) > sum(l[n // 2:]):
		print('YES')
	elif n % 2 == 0 and sum(l[:n // 2 - 1]) > sum(l[n // 2:]):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	sz = int(input())
	l = list(map(int, input().split()))
	ls = sorted(l)
	p = 0
	flag = 0
	a = ls[0]
	b = 0
	for (x, y) in zip(ls[1:], reversed(ls)):
		if x == y:
			break
		a = a + x
		b = b + y
		if a < b:
			print('YES')
			flag = 1
			break
	if flag == 0:
		print('NO')


import sys

def solution(n, nums):
	nums.sort()
	if n <= 2:
		print('NO')
		return
	else:
		red_sum = nums[-1]
		blue_sum = nums[0] + nums[1]
		index = 2
		while blue_sum >= red_sum:
			if index >= n - index:
				print('NO')
				return
			else:
				red_sum += nums[n - index]
				blue_sum += nums[index]
			index += 1
		print('YES')
input = sys.stdin.read().splitlines()
t = int(input[0])
offset = 1
for test in range(t):
	n = input[2 * test + offset]
	nums = input[2 * test + offset + 1].split(' ')
	nums = [int(e) for e in nums]
	solution(int(n), nums)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	sum_blue = a[0] + a[1]
	sum_red = a[-1]
	it_blue = 2
	it_red = len(a) - 2
	while True:
		if sum_blue < sum_red:
			print('YES')
			break
		if it_blue >= it_red:
			print('NO')
			break
		sum_blue += a[it_blue]
		it_blue += 1
		sum_red += a[it_red]
		it_red -= 1