大小为 $n$ 的排列是指一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的序列，其中 $1$ 到 $n$ 之间的每个值恰好出现一次。
如果序列 $b_1, b_2, \dots, b_l$ 可以通过从序列 $a_1, a_2, \dots, a_n$ 中删除某些元素得到（即 $l \leqslant n$ 且存在 $i_1 < i_2 < \dots < i_l$ 使得 $a_{i_t} = b_t$），则称其为序列 $a$ 的子序列。
- 如果序列中的元素 $a_i$ 严格大于其之前的所有元素（即对于所有 $1 \leqslant j < i$ 都有 $a_j < a_i$），则称其为记录。
- 如果序列中的元素 $a_i$ 严格小于其之前的所有元素（即对于所有 $1 \leqslant j < i$ 都有 $a_j > a_i$），则称其为反记录。
给定一个大小为 $n$ 的排列 $p_1, p_2, \dots, p_n$。你需要将其划分为两个非空子序列 $q$ 和 $r$。换句话说，排列 $p$ 中的每个元素必须恰好属于 $q$ 或 $r$ 中的一个。目标是最大化 $q$ 中记录的数量与 $r$ 中反记录的数量之和。
输入格式
每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \leqslant t \leqslant 100\,000$)，表示测试用例的数量。接下来有 $2t$ 行，包含各测试用例的描述。
每个测试用例的第一行包含一个整数 $n$ ($2 \leqslant n \leqslant 200\,000$)，表示排列的大小。
每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示初始排列。保证 $p$ 中的元素包含 $1$ 到 $n$ 的每个数字恰好一次。
所有测试用例的 $n$ 之和不超过 $200\,000$。
输出格式
对于每个测试用例，输出一个整数，表示在最优划分下，$q$ 中记录的数量与 $r$ 中反记录的数量之和的最大值。
子任务
令 $N$ 为单个测试中所有测试用例的 $n$ 之和。
| 子任务 | 分值 | $n, N$ | 附加限制 |
|---|---|---|---|
| 1 | 21 | $n \leqslant 16$ | $t \leqslant 120$ |
| 2 | 22 | $n \leqslant 200, N \leqslant 2000$ | |
| 3 | 14 | $N \leqslant 2000$ | |
| 4 | 10 | $N \leqslant 10\,000$ | |
| 5 | 13 | $N \leqslant 200\,000$ | $p$ 的最长下降子序列长度不超过 $2$ |
| 6 | 20 | $N \leqslant 200\,000$ |
样例
输入 1
4 5 4 1 2 3 5 10 3 8 10 4 1 2 7 9 5 6 3 1 2 3 6 4 2 5 1 6 3
输出 1
5 6 3 5
说明
在第一个测试用例中，一种最优划分 $p$ 为 $q$ 和 $r$ 的方式如下（$q$ 中的记录和 $r$ 中的反记录已标出）：
- $q = 1, 2, 3, 5$
- $r = 4$
在第二个测试用例中，一种最优划分 $p$ 为 $q$ 和 $r$ 的方式如下：
- $q = 3, 8, 4, 1, 2, 9$
- $r = 10, 7, 5, 6$