P11106 [ROI 2023] 峰值 (Day 1)
题目背景
翻译自 [ROI 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。
如果对于所有 $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$ 中的反峰值数量之和的最大值。
说明/提示
前两个样例解释：
设 $N=\sum n$。
| Subtask | 分值 | $n,N$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $21$ | $n\le16$ | $t\le120$ |
| $2$ | $22$ | $n\le200,N\le2000$ | |
| $3$ | $14$ | $N\le2000$ | |
| $4$ | $10$ | $N\le20000$ | |
| $5$ | $13$ | $N\le200000$ | $p$ 的最大递减子序列的长度不超过 $2$ |
| $6$ | $20$ | $N\le200000$ | |