#P11106. [ROI 2023 Day 1] 峰值

    ID: 10393 Type: RemoteJudge 1600ms 512MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>2023Special JudgeROI(俄罗斯)

[ROI 2023 Day 1] 峰值

题目背景

翻译自 ROI 2023 D1T3

如果对于所有 1j<i1 \le j < i,都有 aj<aia_j < a_i,则称 aia_i 为峰值。

如果对于所有 1j<i1 \le j < i,都有 aj>aia_j > a_i,则称 aia_i 为反峰值。

题目描述

给定大小为 nn 的排列 p1,p2,,pnp_1,p_2,\dots,p_n。需要将其分为两个非空子序列 qqrr。每个元素 pp 必须恰好被分到一个子序列中。你需要最大化 qq 中的峰值数量和 rr 中的反峰值数量之和。

输入格式

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

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

每个输入数据集的第二行包含 nn 个整数 p1,p2,,pnp_1,p_2,\dots,p_n,表示原始排列。保证 pp 中的每个数字都恰好出现一次。

每组数据中 nn 的总和不超过 200,000200,000

输出格式

对于每组数据,输出一个整数,表示将 pp 拆分后,qq 中的峰值数量和 rr 中的反峰值数量之和的最大值。

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=nN=\sum n

Subtask 分值 n,Nn,N 特殊性质
11 2121 n16n\le16 t120t\le120
22 2222 n200,N2000n\le200,N\le2000
33 1414 N2000N\le2000
44 1010 N20000N\le20000
55 1313 N200000N\le200000 pp 的最大递减子序列的长度不超过 22
66 2020