# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* shanu_singroha

*abhidot*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1604

# PREREQUISITES:

None

# PROBLEM:

You’re given an array A. Let Z be the sum of its two largest elements.

FInd out whether there exists a rearrangement of A such that A_i + A_{i+1} \lt Z for each 1 \leq i \lt N.

# EXPLANATION:

Let M_1 and M_2 be the two largest elements of A, with M_1 \geq M_2.

It is enough to check whether there exists a rearrangement of A such that no occurrence of M_1 is adjacent to any occurrence of M_2.

There are two possible cases here: M_1 can equal M_2, or they can be different.

- Suppose M_1 = M_2; let this value be M. We want to check whether A can be rearranged such that no two occurrences of M are adjacent.

The absolute best we can do is to place instances of M at alternate positions, i.e, position 1, 3, 5, 7, \ldots

So, the best we can do is \left\lceil \frac{N}{2} \right\rceil positions.

Hence, if the count of M in A exceeds \left\lceil \frac{N}{2} \right\rceil, the answer is`No`

. Otherwise, the answer is`Yes`

. - Suppose M_1 \neq M_2. Then, there is exactly one occurrence of M_1 in A, so we need to check if all the occurrences of M_2 can be placed non-adjacent to it.

Obviously, if every other element is M_2 (i.e M_2 occurs N-1 times) this is impossible.

Otherwise, it’s always possible — for example, place all the occurrences of M_2 at positions 1, 2, 3, \ldots and place M_1 at position N.

So, in this case it’s enough to check whether the count of M_2 equals N-1 or not.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
m1, m2 = a[-1], a[-2]
if m1 == m2:
print('Yes' if a.count(m1) <= (n+1)//2 else 'No')
else:
print('Yes' if a.count(m2) <= n-2 else 'No')
```