Omkar and Bad Story
Contest: Codeforces Round 724 (Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms

Omkar has received a message from Anton saying "Your story for problem A is confusing. Just make a formal statement." Because of this, Omkar gives you an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of $$$n$$$ distinct integers. An array $$$b = [b_1, b_2, \ldots, b_k]$$$ is called nice if for any two distinct elements $$$b_i, b_j$$$ of $$$b$$$, $$$|b_i-b_j|$$$ appears in $$$b$$$ at least once. In addition, all elements in $$$b$$$ must be distinct. Can you add several (maybe, $$$0$$$) integers to $$$a$$$ to create a nice array $$$b$$$ of size at most $$$300$$$? If $$$a$$$ is already nice, you don't have to add any elements.

For example, array $$$[3, 6, 9]$$$ is nice, as $$$|6-3|=|9-6| = 3$$$, which appears in the array, and $$$|9-3| = 6$$$, which appears in the array, while array $$$[4, 2, 0, 6, 9]$$$ is not nice, as $$$|9-4| = 5$$$ is not present in the array.

For integers $$$x$$$ and $$$y$$$, $$$|x-y| = x-y$$$ if $$$x > y$$$ and $$$|x-y| = y-x$$$ otherwise.

Input format:
Each test contains multiple test cases. The first line contains $$$t$$$ ($$$1 \leq t \leq 50$$$), the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1, a_2, \cdots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$) — the elements of the array $$$a$$$.

Output format:
For each test case, output one line containing YES if Omkar can create a nice array $$$b$$$ by adding elements to $$$a$$$ and NO otherwise. The case of each letter does not matter, so yEs and nO will also be accepted.

If the first line is YES, output a second line containing a single integer $$$k$$$ ($$$n \leq k \leq 300$$$).

Then output one line containing $$$k$$$ distinct integers $$$b_1, b_2, \cdots, b_k$$$ ($$$-10^9 \leq b_i \leq 10^9$$$), the elements of the nice array $$$b$$$. $$$b_1, b_2, \cdots, b_k$$$ can be in any order. For each $$$a_i$$$ in $$$a$$$, $$$a_i$$$ must appear at least once in $$$b$$$.

It can be proved that if Omkar can create such an array $$$b$$$, then he can also do so in a way that satisfies the above constraints.

If multiple solutions exist, you can print any.

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

Note:
For the first case, you can add integers to $$$a$$$ to receive the array $$$b = [6, 0, 3, 9]$$$. Note that $$$|6-3| = |9-6| = |3-0| = 3$$$ and $$$3$$$ is in $$$b$$$, $$$|6-0| = |9-3| = 6$$$ and $$$6$$$ is in $$$b$$$, and $$$|9-0| = 9$$$ is in $$$b$$$, so $$$b$$$ is nice.

For the second case, you can add integers to $$$a$$$ to receive the array $$$b = [5, 3, 1, 2, 4]$$$. We have that $$$|2-1| = |3-2| = |4-3| = |5-4| = 1$$$ is in $$$b$$$, $$$|3-1| = |4-2| = |5-3| = 2$$$ is in $$$b$$$, $$$|4-1| = |5-2| = 3$$$ is in $$$b$$$, and $$$|5-1| = 4$$$ is in $$$b$$$, so $$$b$$$ is nice.

For the fourth case, you can add integers to $$$a$$$ to receive the array $$$b = [8, 12, 6, 2, 4, 10]$$$. We have that $$$|4-2| = |6-4| = |8-6| = |10-8| = |12-10| = 2$$$ is in $$$b$$$, $$$|6-2| = |8-4| = |10-6| = |12-8| = 4$$$ is in $$$b$$$, $$$|8-2| = |10-4| = |12-6| = 6$$$ is in $$$b$$$, $$$|10-2| = |12-4| = 8$$$ is in $$$b$$$, and $$$|12-2| = 10$$$ is in $$$b$$$, so $$$b$$$ is nice.

It can be proven that for all other test cases it is impossible to create a nice array $$$b$$$.

Example input:
4
3
3 0 9
2
3 4
5
-7 3 13 -2 8
4
4 8 12 6

Example output:
yes
4
6 0 3 9
yEs
5
5 3 1 2 4
NO
Yes
6
8 12 6 2 4 10

Editorial:
Hint: Consider what happens when $$$a$$$ contains a negative number.
Solution: We first claim that if any negative number exists in $$$a$$$, then no solution exists. Denote $$$p$$$ as the smallest number in $$$a$$$ and $$$q$$$ as another arbitrary number in the array (as $$$n \geq 2$$$, $$$q$$$ always exists). Clearly, $$$|q - p| = q - p > 0$$$. However, because $$$p$$$ is negative, $$$q - p > q$$$. As such, adding $$$q - p$$$ to the output array would create the pair $$$(q - p, p)$$$ with difference $$$q - 2p > q - p$$$. We have the same problem as before; thus, it is impossible to create a nice array if there exists a negative number in $$$a$$$.
After we deal with this case, we now claim that $$$b = [0, 1, 2, ..., 100]$$$ is a valid nice array for any $$$a$$$ that contains no negative numbers. It is easy to verify that this is a valid nice array. And since in this case, every element of $$$a$$$ is nonnegative and distinct, it is always possible to rearrange and add elements to $$$a$$$ to obtain $$$b$$$.