CF1536D Omkar and Medians

糟糕！Ray 又一次丢失了他的数组！不过，Omkar 也许能帮上忙，因为他认为自己找到了 Ray 的数组的 OmkArray。对于一个包含元素 $a_1, a_2, \ldots, a_{2k-1}$ 的数组 $a$，其 OmkArray 是一个包含元素 $b_1, b_2, \ldots, b_k$ 的数组 $b$，其中 $b_i$ 等于 $a_1, a_2, \ldots, a_{2i-1}$ 的中位数，对所有 $i$ 都成立。Omkar 找到了一个长度为 $n$ 的数组 $b$（$1 \leq n \leq 2 \cdot 10^5$，$-10^9 \leq b_i \leq 10^9$）。给定这个数组 $b$，Ray 想要验证 Omkar 的说法，看看是否真的存在某个数组 $a$，使得 $b$ 是 $a$ 的 OmkArray。你能帮 Ray 吗？ 对于一组数 $a_1, a_2, \ldots, a_{2i-1}$，其中位数定义为：将 $a_1, a_2, \ldots, a_{2i-1}$ 按非递减顺序排序后，取第 $i$ 个数 $c_i$。

每个测试包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，输出一行，如果存在某个数组 $a$，使得对所有 $i$，$b_i$ 是 $a_1, a_2, \dots, a_{2i-1}$ 的中位数，则输出 YES，否则输出 NO。YES 和 NO 的大小写不敏感（如 yEs 和 No 也被接受）。

在第一个样例的第二个测试用例中，数组 $[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。 由 ChatGPT 4.1 翻译