Omkar and Medians

对于一个长度为 $2\times k-1$ 的序列 $a$，我们定义一个长度为 $k$ 的序列 $b$ 是 $a$ 的 _Omk序列_ 仅当其满足对于任意整数 $i\in[1,k]$，$b_i$ 的值等于 $a_1,a_2,\cdots,a_{2\times i-1}$ 这 $2\times i-1$ 个数的中位数。 现在给定 $k$ 和一个长度为 $k$ 的序列 $b$，你需要判断是否存在长度为 $2\times k-1$ 的序列 $a$ 使得 $b$ 是 $a$ 的 _Omk序列_。 $T$ 组数据。 $1\leq T\leq10^4;1\leq n,\sum n\leq2\times10^5;|b_i|\leq10^9;$

Uh oh! Ray lost his array yet again! However, Omkar might be able to help because he thinks he has found the OmkArray of Ray's array. The OmkArray of an array $ a $ with elements $ a_1, a_2, \ldots, a_{2k-1} $ , is the array $ b $ with elements $ b_1, b_2, \ldots, b_{k} $ such that $ b_i $ is equal to the median of $ a_1, a_2, \ldots, a_{2i-1} $ for all $ i $ . Omkar has found an array $ b $ of size $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ -10^9 \leq b_i \leq 10^9 $ ). Given this array $ b $ , Ray wants to test Omkar's claim and see if $ b $ actually is an OmkArray of some array $ a $ . Can you help Ray? The median of a set of numbers $ a_1, a_2, \ldots, a_{2i-1} $ is the number $ c_{i} $ where $ c_{1}, c_{2}, \ldots, c_{2i-1} $ represents $ a_1, a_2, \ldots, a_{2i-1} $ sorted in nondecreasing order.

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the array $ b $ . The second line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ -10^9 \leq b_i \leq 10^9 $ ) — the elements of $ b $ . It is guaranteed the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output one line containing YES if there exists an array $ a $ such that $ b_i $ is the median of $ a_1, a_2, \dots, a_{2i-1} $ for all $ i $ , and NO otherwise. The case of letters in YES and NO do not matter (so yEs and No will also be accepted).

5
4
6 2 1 3
1
4
5
4 -8 5 6 -7
2
3 3
4
2 1 2 3

NO
YES
NO
YES
YES

5
8
-8 2 -6 -5 -4 3 3 2
7
1 1 3 1 0 -2 -1
7
6 12 8 6 2 6 10
6
5 1 2 3 6 7
5
1 3 4 3 0

NO
YES
NO
NO
NO

In the second case of the first sample, the array $ [4] $ will generate an OmkArray of $ [4] $ , as the median of the first element is $ 4 $ . In the fourth case of the first sample, the array $ [3, 2, 5] $ will generate an OmkArray of $ [3, 3] $ , as the median of $ 3 $ is $ 3 $ and the median of $ 2, 3, 5 $ is $ 3 $ . In the fifth case of the first sample, the array $ [2, 1, 0, 3, 4, 4, 3] $ will generate an OmkArray of $ [2, 1, 2, 3] $ as - the median of $ 2 $ is $ 2 $ - the median of $ 0, 1, 2 $ is $ 1 $ - the median of $ 0, 1, 2, 3, 4 $ is $ 2 $ - and the median of $ 0, 1, 2, 3, 3, 4, 4 $ is $ 3 $ . In the second case of the second sample, the array $ [1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5] $ will generate an OmkArray of $ [1, 1, 3, 1, 0, -2, -1] $ , as - the median of $ 1 $ is $ 1 $ - the median of $ 0, 1, 4 $ is $ 1 $ - the median of $ 0, 1, 3, 4, 5 $ is $ 3 $ - the median of $ -2, -2, 0, 1, 3, 4, 5 $ is $ 1 $ - the median of $ -4, -2, -2, -2, 0, 1, 3, 4, 5 $ is $ 0 $ - the median of $ -4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5 $ is $ -2 $ - and the median of $ -4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5 $ is $ -1 $ For all cases where the answer is NO, it can be proven that it is impossible to find an array $ a $ such that $ b $ is the OmkArray of $ a $ .