题目描述
我们定义一个序列的权值为 $ \max($前缀最大值个数，后缀最大值个数$) $。 给定一个长度为 $ n $ 的首尾相接的排列 $ p $，你需要将其分成 $ k $ 段非空序列，使得每个数都恰好在一段里，且 $ k $ 段序列的权值之和尽可能大。
输入格式
第一行两个正整数 $ n, k $，表示排列长度和划分段数。 第二行输入 $ n $ 个正整数，表示排列 $ p $。
输出格式
一行一个整数，表示最大权值和。
输入样例1
6 1
4 1 6 2 5 3输出样例1
4样例解释1
切开 $ 1 $ 到 $ 6 $ 的边，变为序列 $\{6,2,5,3,4,1\}$，该序列的后缀最大值有 $ \{6, 5, 4, 1\} $ 四个数。
输入样例2
6 2
4 1 6 2 5 3输出样例2
5样例解释2
切开 $ 1 $ 到 $ 6 $，$ 2 $ 到 $ 5 $ 的边，分成序列 $\{6,2\}$ 和 $ \{5,3,4,1\}$，权值分别为 $ 2 $ 和 $ 3 $，权值之和为 $ 5 $。
输入样例3
18 3
4 6 1 12 15 14 17 13 9 10 5 18 2 8 16 11 3 7输出样例3
12数据范围
对于所有数据，满足 $ 1 \le k \le n \le 6 \times 10^5, 1 \le k \le 30 $，保证输入的是一个 $ \{1, 2, \cdots, n\} $ 的排列。
| 子任务编号 | $n$ | $k$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $\le 30$ | - | - | $10$ |
| $2$ | - | $k=1$ | $10$ | |
| $3$ | $\le 2\,000$ | - | 数据随机 | $20$ |
| $4$ | $\le 5\,000$ | - | $20$ | |
| $5$ | $\le 5 \times 10^4$ | $20$ | ||
| $6$ | - | $20$ |
数据随机：输入的排列在 $ n! $ 种排列中随机生成。