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.util.*;
import java.io.*;

import static java.lang.Math.*;

public class Main
{
    static MyScanner scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 2_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null, null, "_", 1 << 27) {
            public void run() {
                try {
                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

    static int n,k, arr[], next[];
    static int lazy[][], tree[][];
    static void solve() throws java.lang.Exception {
        //initIo(true, "");
        initIo(false, "");
        StringBuilder sb = new StringBuilder();

        n = ni();
        k = ni();
        int sz = 4*n;
        lazy = new int[k+1][sz];
        tree = new int[k+1][sz];
        arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = ni();
        }
        next = new int[n];
        HashMap<Integer, Integer> last = new HashMap<>();
        Arrays.fill(next, -1);
        for(int i=n-1;i>=0;--i) {
            if(last.containsKey(arr[i])) {
                next[i] = last.get(arr[i]);
            }
            last.put(arr[i], i);
        }

        // pa("next", next);

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

        // pa("dp[0]", dp[0]);
        for(int i=0;i<n;i++) {
            rangeUpdate(0, i, i, dp[0][i+1]);
        }

        for(int i=1;i<k;i++) {
            for(int j=n-1;j>=0;--j) {
                // pl("i: "+i+" j: "+j);
                if(next[j]!=-1) {
                    rangeUpdate(i-1, next[j], n-1, (next[j] - j));
                }
                // pa("tree", tree[i-1]);
                if(j==n-1) {
                    dp[i][j] = 0;
                }
                else {
                    dp[i][j] = query(i - 1, j, n - 1);
                    // pl("setting dp[i][j]: "+dp[i][j]);
                }
                rangeUpdate(i, j, j, dp[i][j+1]);
            }
        }

        // pa("dp", dp);
        pl(dp[k-1][0]);

        pw.flush();
        pw.close();
    }

    static void rangeUpdate(int treeidx,int l,int r,int val)
    {
        rangeUpdate(treeidx,1,0,n-1,l,r,val);
    }
    static int query(int treeidx,int l,int r)
    {
        return query(treeidx,1,0,n-1,l,r);
    }
    static void rangeUpdate(int treeidx,int treein,int low,int high,int l,int r,int val)
    {
        if(lazy[treeidx][treein]!=0)
        {
            tree[treeidx][treein]+=lazy[treeidx][treein];
            if(low!=high)
            {
                lazy[treeidx][(treein<<1)]+=lazy[treeidx][treein];
                lazy[treeidx][1+(treein<<1)]+=lazy[treeidx][treein];
            }
            lazy[treeidx][treein] = 0;
        }
        if(l<=low && high<=r)
        {
            tree[treeidx][treein]+=val;
            if(low!=high)
            {
                lazy[treeidx][treein<<1]+=val;
                lazy[treeidx][1+(treein<<1)]+=val;
            }
            return;
        }
        if(low>r || high<l)
            return;
        int mid = (low+high)>>1;
        rangeUpdate(treeidx,(treein<<1),low,mid,l,r,val);
        rangeUpdate(treeidx,1 + (treein<<1),mid+1,high,l,r,val);
        tree[treeidx][treein] = min(tree[treeidx][(treein<<1)], tree[treeidx][1+(treein<<1)]);
//        for(int i=l;i<=r;i++) {
//            tree[treeidx][i]+=val;
//        }
    }
    static int query(int treeidx,int treein,int low,int high,int l,int r)
    {
        if(lazy[treeidx][treein]!=0)
        {
            tree[treeidx][treein]+=lazy[treeidx][treein];
            if(low!=high)
            {
                lazy[treeidx][(treein<<1)]+=lazy[treeidx][treein];
                lazy[treeidx][1+(treein<<1)]+=lazy[treeidx][treein];
            }
            lazy[treeidx][treein] = 0;
        }
        if(l<=low && high<=r)
            return tree[treeidx][treein];
        if(low>r || high<l)
            return Integer.MAX_VALUE;
        int mid = (low+high)>>1;
        return min(query(treeidx,1+(treein<<1),mid+1,high,l,r), query(treeidx,(treein<<1),low,mid,l,r));
//        long min = Long.MAX_VALUE;
//        for(int i=l;i<=r;i++) {
//            min = min(min, tree[treeidx][i]);
//        }
//        return min;
    }

    static void assert_in_range(String varName, int n, int l, int r) {
        if (n >=l && n<=r) return;
        System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
        System.exit(1);
    }
    static void assert_in_range(String varName, long n, long l, long r) {
        if (n>=l && n<=r) return;
        System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
        System.exit(1);
    }

    static void initIo(boolean isFileIO, String suffix) throws IOException {
        scan = new MyScanner(isFileIO, suffix);
        if(isFileIO) {
            pw = new PrintWriter("/Users/dsds/Desktop/output"+suffix+".txt");
        }
        else {
            pw = new PrintWriter(System.out, true);
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }

    static void pa(String arrayName, TreeSet<Integer> set)
    {
        pl(arrayName+" : ");
        for(Object o : set)
            p(o);
        pl();
    }

    static void pa(String arrayName, boolean arr[])
    {
        pl(arrayName+" : ");
        for(boolean o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, boolean[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(boolean o : arr[i])
                p(o);
            pl();
        }
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner(boolean readingFromFile, String suffix) throws IOException
        {
            if(readingFromFile) {
                br = new BufferedReader(new FileReader("/Users/ddfds/Desktop/input"+suffix+".txt"));
            }
            else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}