## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Doubled Distances CodeChef Solution | CodeChef Problem Solution 2022

You are given $N$ integers $\left\{{A}_{1},{A}_{2},\dots ,{A}_{N}\right\}$. Determine whether they can be reordered such that each pair of consecutive differences differ by a factor of $2$.

Formally, determine whether there exists a rearrangement of the given integers into an array $\left[{B}_{1},{B}_{2},\dots ,{B}_{N}\right]$ such that, for each $2\le i\le N-1$at least one of the following two conditions holds:

• ${B}_{i}-{B}_{i-1}=2\cdot \left({B}_{i+1}-{B}_{i}\right)$or
• $2\cdot \left({B}_{i}-{B}_{i-1}\right)={B}_{i+1}-{B}_{i}$

Note that different conditions can hold at different indices — the only restriction is that at each index, at least one of the given conditions must hold. Please see the sample tests below for examples.

### Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases. The description of $T$ test cases follows.

• Each test case consists of two lines of input.
• The first line of each test case contains a single integer, $N$.
• The second line of each test case contains $N$ space-separated integers, denoting ${A}_{1},{A}_{2},\dots ,{A}_{N}$.

### Output Format

For each test case, output in a single line the answer — $\mathtt{\text{YES}}$ if a rearrangement that satisfies the given conditions exists, and $\mathtt{\text{NO}}$ otherwise.

The output is not case sensitive, so for example the strings $\mathtt{\text{YES, Yes, yES}}$, etc. will all be treated as correct.

### Constraints

• $1\le T\le 100$
• $3\le N\le {10}^{5}$
• $0\le {A}_{i}\le {10}^{9}$
• The sum of $N$ across all test cases won't exceed ${10}^{5}$

### Sample Input 1

4
3
5 2 4
5
2 1 16 8 4
5
97 98 100 96 88
6
16 19 18 21 24 22


### Sample Output 1

Yes
Yes
No
Yes


### Explanation

Test case $1$: Rearrange the numbers to form $\left[5,4,2\right]$. The consecutive differences are $\left[4-5,2-4\right]=\left[-1,-2\right]$, and $-2=2\cdot \left(-1\right)$.

Test case $2$: One possible rearrangement is $\left[1,2,4,8,16\right]$. The consecutive differences are consecutive powers of $2$.

Test case $3$: No rearrangement of the numbers satisfies the condition. For example, one rearrangement is $\left[97,98,100,96,88\right]$ with consecutive differences $\left[1,2,-4,-8\right]$$2$ and $-4$ do not differ by a factor of $2$ (they differ by a factor of $-2$), so this is not a valid arrangement.