Problem: You are given an array a of n integers. Define the cost of some array t as follows:

$$$cost(t) = ∑_{x ∈ set(t) } last(x) - first(x),$$$ 

where set(t) is the set of all values in t without repetitions, first(x), and last(x) are the indices of the first and last occurrence of x in t, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array a into k consecutive segments such that each element of a belongs to exactly one segment and the sum of the cost of individual segments is minimum.

Input

The first line contains two integers n, k (1 ≤ n ≤ 35 000, 1 ≤ k ≤ min(n,100)).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

Output

Output the minimum sum of the cost of individual segments.

Examples

Input


7 2
1 6 6 4 6 6 6


Output


3


Input


7 4
5 5 5 5 2 3 3


Output


1

Note

In the first example, we can divide the array into [1,6,6,4] and [6,6,6]. Cost of [1,6,6,4] will be (1-1) + (3 - 2) + (4-4) = 1 and cost of [6,6,6] will be 3-1 = 2. Total cost would be 1 + 2 = 3.

In the second example, divide the array into [5,5],[5],[5,2,3] and [3]. Total Cost would be 1 + 0 + 0 + 0 = 1.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main{
	static long[]memo,sTree,lazy;
	static int N;
	static long inf=(long)1e15;
	static void build(int node,int left,int right) {
		if(left==right) {
			if(left>=memo.length) {
				sTree[node]=inf;//the value that won't affect the required operation
				lazy[node]=0;
			}
			else {
				sTree[node]=memo[left];
				lazy[node]=0;
				memo[left]=inf;
			}
			return;
		}
		int mid=(left+right)>>1;
		int leftChild=node<<1,rightChild=node<<1|1;
		build(leftChild, left, mid);
		build(rightChild, mid+1, right);
		sTree[node]=Math.min(sTree[leftChild],sTree[rightChild]);
		lazy[node]=0;
	}
	static long query(int left,int right) {
		return query(1, 1, N, left, right);
	}
	static long query(int node,int curLeft,int curRight,int left,int right) {
		if(curLeft>right || curRight<left)return inf;//the value that won't affect the required operation
		
		if(curLeft>=left && curRight<=right) {
			return sTree[node];
		}
		int mid=(curLeft+curRight)>>1;
		int leftChild=node<<1,rightChild=node<<1|1;
		long q1=query(leftChild, curLeft, mid, left, right);
		long q2=query(rightChild, mid+1, curRight, left, right);
		
		return Math.min(q1, q2);
	}
	
	static void update_range(int i, int j, int val){
		update_range(1,1,N,i,j,val);
	}
	
	static void update_range(int node,int curLeft,int curRight,int left,int right,int val) {
		if(curLeft>right || curRight<left)return;
		
		if(curLeft>=left && curRight<=right) {
			sTree[node] += val;			
			lazy[node] += val;
			return;
		}
		int mid=(curLeft+curRight)>>1;
		int leftChild=node<<1,rightChild=node<<1|1;
		propagate(node, curLeft, mid, curRight);
		update_range(leftChild, curLeft, mid, left, right,val);
		update_range(rightChild, mid+1, curRight, left, right,val);
		
		sTree[node]=Math.min(sTree[leftChild],sTree[rightChild]);
		
	}
	
	static void propagate(int node, int b, int mid, int e){
		lazy[node<<1] += lazy[node];
		lazy[node<<1|1] += lazy[node];
		sTree[node<<1] += lazy[node];		
		sTree[node<<1|1] += lazy[node];		
		lazy[node] = 0;//the value that won't affect the required operation
	}
	
	static void main() throws Exception{
		int n=sc.nextInt(),k=sc.nextInt();
		int[]in=sc.intArr(n);
		
		N=1;
		while(N<n+2) {
			N<<=1;
		}
		sTree=new long[N<<1];
		lazy=new long[N<<1];
		memo=new long[n+2];
		for(int i=2;i<=n+1;i++)memo[i]=inf;
		for(int curk=1;curk<=k;curk++) {
			build(1, 1, N);
			int[]lastOcc=new int[n+1];
			for(int i=2;i<=n+1;i++) {
				int x=in[i-2];
				if(lastOcc[x]!=0) {
					update_range(1, lastOcc[x]-1, i-lastOcc[x]);
				}
				memo[i]=query(1, i-1);
				lastOcc[x]=i;
			}
		}
		pw.println(memo[n+1]);
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc=1;
//        tc=sc.nextInt();
		for(int i=1;i<=tc;i++) {
//			pw.printf("Case #%d: ", i);
			main();
		}
		
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
	 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
	 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
	 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
	 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
	 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	 
		public boolean ready() throws IOException {
			return br.ready();
		}
	 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
		
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}