题目描述

给定一个整数排列 $P_1, P_2, \\dots, P_N$，其中的元素为 $1$ 到 $N$ 的整数。你能将它拆分成两个子序列，使得两个子序列的最长递增子序列长度相等吗？

具体地说，你的目标是找到两个整数序列 $a$ 和 $b$，满足以下条件：

• $a$ 和 $b$ 都是 $P$ 的子序列。
• 整数 $i = 1, 2, \\cdots, N$ 在 $a$ 和 $b$ 中恰好出现一次。
• （$a$ 的最长递增子序列的长度）$=$（$b$ 的最长递增子序列的长度）

判断是否可以实现这个目标。

输入包含 $T$ 个测试用例，请解决每个测试用例。

约束条件

• $1 \\le T \\le 2 \\cdot 10^5$
• $1 \\le N \\le 2 \\cdot 10^5$
• $P_1, P_2, \\dots, P_N$ 是 $1$ 到 $N$ 的整数排列。
• 所有测试用例中 $N$ 的总和不超过 $2 \\cdot 10^5$。

输入

从标准输入中按以下格式给出输入。输入的第一行如下所示：

$T$

接下来，有 $T$ 个测试用例，每个测试用例的格式如下：

$N$ $P_1$ $P_2$ $\\dots$ $P_N$

输出

对于每个测试用例，如果可以将排列拆分成两个子序列，使得两个子序列的最长递增子序列长度相等，则输出 YES，否则输出 NO。每个答案占一行。请注意，评判器大小写不敏感：你可以输出大写字母或小写字母。

示例输入 1

5
1
1
2
2 1
3
1 2 3
5
1 3 5 2 4
6
2 3 4 5 6 1

示例输出 1

NO
YES
NO
YES
NO

\[1, 3, 5, 2, 4\] 可以被拆分成 \[1, 5\] 和 \[3, 2, 4\]，两者的最长递增子序列长度都为 2。

而无法将 \[2, 3, 4, 5, 6, 1\] 拆分成两个长度相等的子序列，使得它们的最长递增子序列长度相等。