题目描述

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