题目描述

“一个平民竟然妄想坐在我旁边。认清你的身份！” ——克莱尔·弗朗索瓦

这是本题的简单版本。简单版与困难版的唯一区别是，困难版要求你构造一棵满足条件的树。

作为一名土系法师，雷掌握了种树的法术！但玛娜莉亚吹嘘她能种出更特别的树种。雷记得最稀有的树可以用一个特定的排列公式来培育——请帮她判断这样的排列是否能对应一棵合法的树！

给定一个长度为 $n$ 的排列 $p$，判断是否存在一棵有 $n$ 个顶点（编号为 $1, 2, \dots, n$）的无向树，满足以下条件：

• 对于树中任意一条边连接的两个顶点 $u$ 和 $v$（满足 $1 \leq u < v \leq n$），$u$ 在排列 $p$ 中出现的位置早于 $v$。

注：排列是指包含 $1$ 到 $n$ 每个整数恰好一次的数组。

输入格式

• 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。
• 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 顶点的数量。
• 每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$）—— 给定的排列，保证所有元素互不相同。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 "Yes" 如果存在满足条件的树，否则输出 "No"。

输出不区分大小写（例如 "yEs"、"yes"、"YES" 均视为合法答案）。

样例输入

9
6
1 3 4 5 2 6
4
3 4 1 2
5
4 3 5 1 2
4
1 2 3 4
7
4 3 5 7 6 2 1
6
2 4 6 1 3 5
3
2 1 3
4
2 4 1 3
6
4 2 6 5 1 3

样例输出

Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

提示

在第一个样例中，可构造如下边集的树：

• $\{3, 1\}$（$1 < 3$ 且 $1$ 在 $p$ 中早于 $3$）
• $\{4, 1\}$（$1 < 4$ 且 $1$ 在 $p$ 中早于 $4$）
• $\{6, 5\}$（$5 < 6$ 且 $5$ 在 $p$ 中早于 $6$）
• $\{6, 2\}$（$2 < 6$ 且 $2$ 在 $p$ 中早于 $6$）
• $\{6, 1\}$（$1 < 6$ 且 $1$ 在 $p$ 中早于 $6$）

第二个样例中，不存在满足约束条件的树。