We define the weight of a sequence as $\max(\text{number of prefix maximums, number of suffix maximums})$. Given a cyclic permutation $p$ of length $n$, you need to partition it into $k$ non-empty segments such that every element belongs to exactly one segment, and the sum of the weights of the $k$ segments is maximized.
Input
The first line contains two positive integers $n$ and $k$, representing the length of the permutation and the number of segments, respectively. The second line contains $n$ positive integers, representing the permutation $p$.
Output
Output a single integer representing the maximum sum of weights.
Constraints
For all test cases, $1 \le k \le n \le 6 \times 10^5$ and $1 \le k \le 30$. The input is guaranteed to be a permutation of $\{1, 2, \cdots, n\}$.
| Subtask ID | $n$ | $k$ | Special Property | Score |
|---|---|---|---|---|
| $1$ | $\le 30$ | $10$ | ||
| $2$ | $k=1$ | $10$ | ||
| $3$ | $\le 2\,000$ | Data is random | $20$ | |
| $4$ | $\le 5\,000$ | $20$ | ||
| $5$ | $\le 5 \times 10^4$ | $20$ | ||
| $6$ | $20$ |
Data is random: The input permutation is generated uniformly at random from all $n!$ possible permutations.
Examples
Input 1
6 1 4 1 6 2 5 3
Output 1
4
Note 1
Cutting the edge between $1$ and $6$ results in the sequence $\{6, 2, 5, 3, 4, 1\}$. The suffix maximums of this sequence are $\{6, 5, 4, 1\}$, which gives a count of $4$.
Input 2
6 2 4 1 6 2 5 3
Output 2
5
Note 2
Cutting the edges between $1$ and $6$, and between $2$ and $5$, results in the sequences $\{6, 2\}$ and $\{5, 3, 4, 1\}$. Their weights are $2$ and $3$, respectively, for a total weight sum of $5$.
Input 3
18 3 4 6 1 12 15 14 17 13 9 10 5 18 2 8 16 11 3 7
Output 3
12