The Bakery

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的蛋糕种类序列 $a$。你需要把整个序列恰好划分成 $k$ 个非空连续区间。

一个区间的价值等于其中不同蛋糕种类的数量。求所有区间价值之和的最大值。

输入格式

第一行输入两个整数 $n,k$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示最大价值和。

样例输入 1

4 1
1 2 2 1

样例输出 1

2

样例输入 2

7 2
1 3 3 1 4 4 4

样例输出 2

5

样例输入 3

8 3
7 7 8 7 7 8 1 7

样例输出 3

6

数据范围

对于所有数据，$1\le n\le35000$，$1\le k\le\min(n,50)$，$1\le a_i\le n$。