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.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    long seg[]=new long[4*(35000+3)];
    long lazy[]=new long[4*(35000+3)];
    long dp[]=new long[35000+10];
    long inf = 100000000;
    public  void solve() throws IOException 
    {

        //int t = readInt();
        inf = inf*inf;
        int n = readInt();
        int k = readInt();

        int arr[]=new int[n+1];
        for(int i=1;i<=n;i++)
            arr[i]= readInt();
  

        int next[]=new int[n+1];
        int pan[]=new int[n+1];
        for(int i=n;i>=1;i--)
        {
            if(next[arr[i]]!=0)
            {
                pan[i]= next[arr[i]];
            }
            next[arr[i]]=i;
        }

        
        Arrays.fill(dp,0);
        for(int i=n;i>=1;i--)
        {
            if(pan[i]!=0)
            dp[i]+=pan[i]-i;

            dp[i]= dp[i]+dp[i+1];
        }

        


        for(int j=2;j<=k;j++)
        {
          dp[n+1]=0;
          build(1,n,0);
          Arrays.fill(lazy,0);
          for(int i=n;i>=1;i--)
          {
               if(pan[i]!=0)
               update(1,n,0,pan[i],n,pan[i]-i);

               long val = min(1,n,0,i,n);
               dp[i]= val;
          }
        }
        
     
        out.println(dp[1]);





      
             


         



        



    }
    public  void build(int left , int right, int index )
    {
           if(left==right)
           {
             seg[index]=  dp[left+1];
             return ;
           }

           int mid = left+ (right-left)/2;

           build(left,mid,2*index+1);
           build(mid+1,right, 2*index+2);


           seg[index]=Math.min(seg[2*index+1],seg[2*index+2]);

    }
    public long min( int left, int right, int index, int l , int r )
    {
         if(left>r||l>right)
         {
           return inf;   
         }
         seg[index]= seg[index]+lazy[index];
         if(left!=right)
         {
             lazy[2*index+1]+=lazy[index];
             lazy[2*index+2]+=lazy[index];
             
         }
         lazy[index]=0;

         if(left>=l&&right<=r)
            return seg[index];


        int mid = left+(right-left)/2;
        return Math.min(min(left,mid,2*index+1,l,r),min(mid+1,right,2*index+2,l,r));
    }

    public void  update(int left , int right, int index, int l , int r , int value)
    {
         seg[index]+= lazy[index];
         if(left!=right)
         {
             lazy[2*index+1]+=lazy[index];
             lazy[2*index+2]+=lazy[index];     
         }
         lazy[index]=0;
         if(left>r||l>right)
            return ;
        
         if(left>=l&&right<=r)
         {
            lazy[index]+=value;
            seg[index]+= lazy[index];
            if(left!=right)
            {
             lazy[2*index+1]+=lazy[index];
             lazy[2*index+2]+=lazy[index];     
            }
             lazy[index]=0;
            return ;
         }
         

         
         int mid = left+(right-left)/2;

         update(left,mid,2*index+1,l,r,value);
         update(mid+1,right,2*index+2,l,r,value);
         
         if(left!=right)
         seg[index]=Math.min(seg[2*index+1],seg[2*index+2]);

    }
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v;
    
    edge(int u, int v)
    {
       this.u=u;
       this.v=v;
    }
    public int compareTo(edge e)
    {
        return this.v-e.v;
    }
}