Good Arrays
Contest: Codeforces Round 890 (Div. 2) supported by Constructor Institute
Difficulty rating: 900
Tags: implementation, math

You are given an array of positive integers $$$a$$$ of length $$$n$$$.

Let's call an array of positive integers $$$b$$$ of length $$$n$$$ good if:

1. $$$a_i \neq b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$,
2. $$$a_1 + a_2 +\ldots + a_n = b_1 + b_2 + \ldots + b_n$$$.

Does a good array exist?

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — the elements of the array $$$a$$$.

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

Output format:
For each test case, output "YES" (without quotes) if there exists a good array, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs","yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, a possible good array is $$$[3, 3, 3]$$$. Some examples of not good arrays are:

- $$$[8, 0, 1]$$$ — the array does not consist of only positive integers,
- $$$[5, 2, 4]$$$ — the array does not have the same sum as the given array,
- $$$[5, 2, 2]$$$ — the third element is equal to the third element of the given array.

In the second test case, $$$[1, 1]$$$ is the only array of positive integers of length $$$2$$$ that has the sum of it's elements equal to $$$2$$$. Since $$$[1, 1]$$$ is not a good array, the answer is "NO".

Example input:
6
3
6 1 2
2
1 1
4
3 1 2 4
1
17
5
1 2 1 1 1
3
618343152 819343431 1000000000

Example output:
YES
NO
YES
NO
NO
YES

Editorial:
Suppose $$$b$$$ didn't have to consist of only positive integers. Then, one simple strategy would be to to decrease each of $$$a_2, a_3, \ldots a_n$$$ by $$$1$$$ and increase $$$a_1$$$ by $$$n - 1$$$. Except for $$$n = 1$$$, when it is impossible to get a good array.
When $$$b$$$ has to consist of only positive integers, we can't decrease elements that are equal to $$$1$$$. But to make $$$b_i \neq a_i$$$, we also have to increase them by at least $$$1$$$.
Let $$$cnt_1$$$ be the number of elements in $$$a$$$ that are equal to $$$1$$$. To not change the sum of the array, we have to decrease the other $$$n - cnt_1$$$ elements by at least $$$cnt_1$$$. For this to be possible, their sum must be equal to at least $$$(n - cnt_1) + cnt_1 = n$$$, since each of the $$$n - cnt_1$$$ elements must remain positive. So, $$$a_1 + a_2 + \ldots + a_n$$$ has to be equal to at least $$$cnt_1 + (n - cnt_1) + cnt_1 = cnt_1 + n$$$.
So, if $$$a_1 + \ldots + a_n < cnt_1 + n$$$, a good array doesn't exist. If $$$n = 1$$$, a good array also doesn't exist.
Now suppose $$$a_1 + \ldots + a_n \ge cnt_1 + n$$$ and $$$n \neq 1$$$. We will prove that if this is the case, a good array must exist.
If $$$cnt_1 \le \frac{n}{2}$$$, we increase all $$$a_i = 1$$$ by $$$1$$$ and decrease $$$cnt_1$$$ elements that are $$$\ge 2$$$ by $$$1$$$ and apply the simple strategy described above for the other $$$n - 2 \cdot cnt_1$$$ elements $$$\ge 2$$$, so in this case, a good array exists.
If $$$cnt_1 > \frac{n}{2}$$$, we increase all $$$a_i = 1$$$ by $$$1$$$ and decrease each element $$$\ge 2$$$ by at least $$$1$$$, so $$$b_i \neq a_i$$$ holds for all $$$1 \le i \le n$$$, so in this case, a good array also exists.
Complexity: $$$\mathcal{O}(n)$$$