F. Enigmatic Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on an array $$$a$$$ of length $$$n$$$. They take turns performing the operation. Alice takes the lead. The person who cannot make a move loses.

In an operation, a player can:

  • choose a range $$$[l,r]$$$ ($$$1 \leq l \leq r \leq 10^9$$$);
  • if $$$l \lt r$$$, choose all indices $$$i$$$ such that $$$a_i \in [l,r-1]$$$ and decrease $$$a_i$$$ by $$$1$$$;
  • then, choose some (possibly zero) indices $$$i$$$ such that $$$a_i=r$$$ and decrease $$$a_i$$$ by $$$1$$$.
Afterwards, at least one value of $$$a_i$$$ must have decreased by $$$1$$$. Determine if Alice has a winning strategy.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3\cdot 10^5$$$).

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

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

Output

For each test case, if Alice has a winning strategy, output YES. Otherwise, output NO.

Example
Input
6
7
1 3 1 3 3 4 5
4
1 1 1 1
1
1000000000
3
1 2 3
4
1 2 3 4
8
6 10 9 2 8 6 5 4
Output
YES
YES
NO
NO
YES
NO
Note

In the first test case, Alice can choose the range $$$[1,3]$$$, then choose all indices satisfying $$$a_i \in [1,2]$$$ and decrease $$$a_i$$$ by $$$1$$$. In other words, $$$a_1$$$ and $$$a_3$$$ are decreased by $$$1$$$. After that, $$$a=[0,3,0,3,3,4,5]$$$. Then, Alice can choose some $$$i$$$ satisfying $$$a_i=3$$$. In this case, Alice chooses $$$i=2,4$$$. After that,$$$a=[0,2,0,2,3,4,5]$$$;

It can be proven Alice has a winning strategy after the operation above.

In the second test case, Alice can choose $$$[1,1]$$$. Then, Alice can choose some indices $$$i$$$ satisfying $$$a_i=1$$$. Here, Alice chooses $$$i=1,2,3,4$$$. After this operation, $$$a=[0,0,0,0]$$$ and Alice wins.