题目描述

译自 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

数据范围与提示

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

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