Nearest Point Function
Contest: Kotlin Heroes: Episode 7
Tags: *special, implementation

Your friend has created a nearest point function. For a given array of integer points $$$x$$$ (sorted in ascending order, without any duplicates) and a point $$$y$$$ it can find the nearest point from $$$x$$$ to the point $$$y$$$. In other words, it will find such a point $$$x_i$$$ that $$$|y - x_i|$$$ is the minimum possible, where $$$|a|$$$ is the absolute value of $$$a$$$.

For example, if $$$x = [1, 2, 5, 7, 9, 11]$$$, the answer for $$$y=3$$$ will be $$$2$$$, the answer for $$$y=5$$$ will be $$$5$$$ and the answer for $$$y=100$$$ will be $$$11$$$.

This function is a bit buggy, though. If there are several nearest points to the given one, the function crashes. For example, if $$$x = [1, 2, 5, 7, 9, 11]$$$ (as above) and $$$y=6$$$, the function will crash, since points $$$5$$$ and $$$7$$$ are both the nearest points for $$$6$$$.

Your task is, for a given array of integer points $$$x$$$ (sorted in ascending order, without any duplicates), determine if it is possible to cause the function to crash by choosing some integer point $$$y$$$.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of points in the array $$$x$$$.

The second line of the test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$), where $$$x_i$$$ is the $$$i$$$-th point in the array $$$x$$$.

All points in the array $$$x$$$ are distinct, and the array $$$x$$$ is sorted in ascending order (in other words, $$$x_1 < x_2 < \ldots < x_n$$$).

The sum of $$$n$$$ over the test cases in the input does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print YES if it is possible to find some integer point $$$y$$$ that will crash the function and NO otherwise.

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

Note:
In the first test case of the example, the function crashes if $$$y = 2$$$ is chosen.

In the fifth test case of the example, the function crashes if $$$y = 500000000$$$ is chosen.

In the sixth test case of the example, the function crashes if $$$y = 10$$$ is chosen.

Example input:
7
2
1 3
2
1 100
3
1 50 101
2
1 1000000000
2
1 999999999
6
1 2 5 7 9 11
6
1 2 5 8 9 12

Example output:
YES
NO
NO
NO
YES
YES
NO

Editorial:
Of course, we can't choose such $$$y$$$ that $$$y < x_1$$$, $$$y > x_n$$$ or $$$y = x_i$$$ for some $$$i$$$, because there will be exactly one nearest point in the array $$$x$$$. So, we need to choose such $$$y$$$ that $$$x_i < y < x_{i + 1}$$$ for some $$$i$$$ from $$$1$$$ to $$$n-1$$$. To make both points $$$x_i$$$ and $$$x_{i + 1}$$$ nearest to the point $$$y$$$, we need to choose $$$y = \frac{x_i + x_{i + 1}}{2}$$$. But this is not always possible, because if $$$x_i$$$ and $$$x_{i + 1}$$$ have different parities, the value $$$y$$$ will be non-integer. So, all we have to do in this problem is to check if there is some pair $$$x_i$$$ and $$$x_{i + 1}$$$ that they have the same parity. If there is such a pair, we can break the function, otherwise we can't. Choosing non-adjacent values in $$$x$$$ is wrong, though, because if we choose such $$$x_i$$$ and $$$x_j$$$ that $$$|j - i| > 1$$$ then there will be other points from $$$x$$$ that are nearest to the point $$$y = \frac{x_i + x_j}{2}$$$ (i.e. either $$$x_i$$$ or $$$x_j$$$ will not be the nearest point to $$$y$$$ in such a case).