呃哦!雷的阵法再次失效!不过,奥姆卡也许能帮上忙,因为他认为自己已经找到了雷阵的奥姆卡阵列。包含元素 $$$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 的声明并查看 $$$b$$$ 实际上是否是某个数组 $$$a$$$ 的 OmkArray。你能帮助雷吗?
一组数字 $$$a_1, a_2, \ldots, a_{2i-1}$$$ 的中位数是数字 $$$c_{i}$$$,其中 $$$c_{1}, c_{2}, \ldots, c_{2i-1}$$$ 代表 $$$a_1, a_2, \ldots, a_{2i-1}$$$ 按非降序排序。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$ 且 $$$b_i$$$ 是所有 $$$i$$$ 的 $$$a_1, a_2, \dots, a_{2i-1}$$$ 的中位数,则输出一行包含 YES,否则输出 NO。 YES 和 NO 中字母的大小写并不重要(因此 yE 和 No 也将被接受)。
示例
输入 #1
5 4 6 2 1 3 1 4 5 4 -8 5 6 -7 2 3 3 4 2 1 2 3
输出 #1
NO YES NO YES YES
输入 #2
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
输出 #2
NO YES NO NO NO
注意
在第一个样本的第二种情况下,数组 $$$[4]$$$ 将生成 $$$[4]$$$ 的 OmkArray,因为第一个元素的中位数是 $$$4$$$。
在第一个样本的第四种情况中,数组 $$$[3, 2, 5]$$$ 将生成 $$$[3, 3]$$$ 的 OmkArray,因为 $$$3$$$ 的中位数是 $$$3$$$,$$$2, 3, 5$$$ 的中位数是 $$$3$$$。
在第一个样本的第五种情况中,数组 $$$[2, 1, 0, 3, 4, 4, 3]$$$ 将生成 $$$[2, 1, 2, 3]$$$ 的 OmkArray,如下所示
- $$$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]$$$ 将生成 $$$[1, 1, 3, 1, 0, -2, -1]$$$ 的 OmkArray,如下
- $$$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$$$
对于所有答案为“否”的情况,可以证明不可能找到一个数组 $$$a$$$ 使得 $$$b$$$ 是 $$$a$$$ 的 OmkArray。