题目背景

翻译自 ROI 2023 D1T3。

如果对于所有 $1 \le j < i$，都有 $a_j < a_i$，则称 $a_i$ 为峰值。

如果对于所有 $1 \le j < i$，都有 $a_j > a_i$，则称 $a_i$ 为反峰值。

题目描述

给定大小为 $n$ 的排列 $p_1,p_2,\dots,p_n$。需要将其分为两个非空子序列 $q$ 和 $r$。每个元素 $p$ 必须恰好被分到一个子序列中。你需要最大化 $q$ 中的峰值数量和 $r$ 中的反峰值数量之和。

输入格式

每个测试点由多组数据组成。第一行包含一个整数 $t(1 \le t \le 100,000)$，表示数据组数。接下来的 $2t$ 行，每两行是一组数据。

每组数据的第一行包含一个整数 $n(2 \le n \le 200,000)$，表示排列的大小。

每个输入数据集的第二行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$，表示原始排列。保证 $p$ 中的每个数字都恰好出现一次。

每组数据中 $n$ 的总和不超过 $200,000$。

输出格式

对于每组数据，输出一个整数，表示将 $p$ 拆分后，$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=\sum n$。