题目描述

译自 ROI 2023 Day1 T3. Рекорды и антирекорды

长度为 $n$ 的排列是指一个由 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ 组成的序列，其中从 $1$ 到 $n$ 的每个数都恰好出现一次。

如果可以通过从 $a$ 中删除一些元素得到 $b$，那么我们称序列 $b_{1}, b_{2}, \ldots, b_{l}$ 是序列 $a_{1}, a_{2}, \ldots, a_{n}$ 的子序列。（也就是说 $l \leq n$ 并且存在 $i_{1}<i_{2}<\ldots<i_{l}$ 使得 $a_{i_{t}}=b_{t}$ ）

• 如果序列 $a$ 中的第 $i$ 个元素 $a_{i}$ 严格大于所有前面的元素，它被称为前缀最大值（也就是说对于所有 $1 \leq j<i$，都有 $a_{j}<a_{i}$）。
• 如果序列 $a$ 中的第 $i$ 个元素 $a_{i}$ 严格小于所有前面的元素，它被称为前缀最小值（也就是说对于所有 $1 \leq j<i$，都有 $a_{j}>a_{i}$）。

给定一个长度为 $n$ 的排列 $p_{1}, p_{2}, \ldots, p_{n}$。要求把它分成两个非空的子序列 $q$ 和 $r$。换句话说，$p$ 中每个元素必须恰好属于一个子序列。同时要求最大化 $q$ 中前缀最大值的数量和 $r$ 中前缀最小值的数量的和。

输入格式

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 10^5)$，表示测试数据的组数。接下来的 $2t$ 行每两行描述了一组测试数据：

每组测试数据的第一行包含一个整数 $n\ (2 \leq n \leq 2\times 10^5)$，表示排列的长度。

每组测试数据的第二行包含 $n$ 个整数 $p_{1}, p_{2}, \ldots, p_{n}$，表示原始的排列。保证在 $p$ 中 $1$ 到 $n$ 的每个数都恰好出现一次。

所有测试数据中的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示在最优的划分方案下，$q$ 中前缀最大值的数量和 $r$ 中前缀最小值的数量的和的最大值。

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

5
6
3
5

在第一个测试数据中，一种最优的划分方案是（$q$ 中的前缀最大值和 $r$ 中的前缀最小值被框了起来）：

• $q = \boxed{1}~\boxed{2}~\boxed{3}~\boxed{5}$
• $r = \boxed{4}$

在第二个测试数据中，一种最优的划分方案是：

• $q = \boxed{3}~\boxed{8}~4~1~2~\boxed{9}$
• $r = \boxed{10}~\boxed{7}~\boxed{5}~6$

数据范围与提示

令 $N$ 表示一个测试点中所有 $n$ 的和。其中子任务 $0$ 是样例。

详细子任务附加限制及分值如下表所示。