题目描述

我们定义一个序列的权值为 $\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!$ 种排列中随机生成。