CF1536D.Omkar and Medians

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.

哎呀！雷又弄丢了他的数组！不过，奥姆卡尔或许能帮忙，因为他觉得自己找到了雷的数组的“奥姆卡尔数组”（OmkArray）。对于一个含有元素 $a_1, a_2, \ldots, a_{2k-1}$ 的数组 $a$，其奥姆卡尔数组（OmkArray）是数组 $b$，其元素为 $b_1, b_2, \ldots, b_{k}$，其中对每个 $i$，$b_i$ 等于 $a_1, a_2, \ldots, a_{2i-1}$ 的中位数。奥姆卡尔找到了一个长度为 $n$ 的数组 $b$（$1 \leq n \leq 2 \cdot 10^5$，$-10^9 \leq b_i \leq 10^9$）。给定该数组 $b$，雷想验证奥姆卡尔的说法是否成立：$b$ 是否确实是某个数组 $a$ 的奥姆卡尔数组？你能帮雷吗？

一组数 $a_1, a_2, \ldots, a_{2i-1}$ 的中位数是指：将 $a_1, a_2, \ldots, a_{2i-1}$ 按非递减顺序排序后得到序列 $c_1, c_2, \ldots, c_{2i-1}$，则中位数为 $c_i$。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $b$ 的长度。

第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \leq b_i \leq 10^9$），即数组 $b$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $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).

对于每个测试用例，如果存在一个数组 $a$，使得对所有 $i$，$b_i$ 均为 $a_1, a_2, \dots, a_{2i-1}$ 的中位数，则输出一行 YES；否则输出 NO。YES 和 NO 的大小写不敏感（因此 yEs 和 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$.

在第一个样例的第二种情况中，数组 $[4]$ 将生成 OmkArray $[4]$，因为首个元素的中位数为 $4$。

在第一个样例的第四种情况中，数组 $[3, 2, 5]$ 将生成 OmkArray $[3, 3]$，因为 $3$ 的中位数为 $3$，而 $2, 3, 5$ 的中位数为 $3$。

在第一个样例的第五种情况中，数组 $[2, 1, 0, 3, 4, 4, 3]$ 将生成 OmkArray $[2, 1, 2, 3]$，因为：

• $2$ 的中位数为 $2$；
• $0, 1, 2$ 的中位数为 $1$；
• $0, 1, 2, 3, 4$ 的中位数为 $2$；
• $0, 1, 2, 3, 3, 4, 4$ 的中位数为 $3$。

在第二个样例的第二种情况中，数组 $[1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5]$ 将生成 OmkArray $[1, 1, 3, 1, 0, -2, -1]$，因为：

• $1$ 的中位数为 $1$；
• $0, 1, 4$ 的中位数为 $1$；
• $0, 1, 3, 4, 5$ 的中位数为 $3$；
• $-2, -2, 0, 1, 3, 4, 5$ 的中位数为 $1$；
• $-4, -2, -2, -2, 0, 1, 3, 4, 5$ 的中位数为 $0$；
• $-4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5$ 的中位数为 $-2$；
• $-4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5$ 的中位数为 $-1$。

对于所有答案为 NO 的情况，均可证明：不存在数组 $a$，使得 $b$ 是 $a$ 的 OmkArray。