Given an array contains ~n~ integers ~[a_1, a_2, ..., a_n]~. The value of a subarray ~^\dagger~ is the number of different values in it. Divide the above array into ~k~ consecutive subarrays so that the total value of the subarrays is as large as possible.

Example: With ~n = 7~ and ~k = 2~, the array ~[1, 3, 3, 1, 4, 4, 4]~ has a largest sum of value is ~5~ when the array is divided into ~k = 2~ subarrays ~[1, 3]~ and ~[3, 1, 4, 4, 4]~.

~\dagger~ A subarray is obtained by removing some (possibly zero) elements from the beginning or end of the array.

Input

• The first line contains two integers ~n~ and ~k~ (~1 \le n \le 35000~, ~1 \le k \le min(n, 50)~).
• The second line contains ~n~ integers ~a_1, a_2, ..., a_n~ (~1 \le a_i \le n~).

Output

• Print the only integer - the largest sum value of subarrays.

Samples

Sample Input 1

4 1
1 2 2 1

Sample Output 1

2

Sample Input 2

7 2
1 3 3 1 4 4 4

Sample Output 2

5

Sample Input 3

8 3
7 7 8 7 7 8 1 7

Sample Output 3

6