#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 35005;
const int K = 101;

int a[N];

int dp[K][N];

int color[N],d[N];
int cut_value[N];

int get_cost(int l,int r) {
  assert(l<=r);
  return dp[1][r] - dp[1][l-1] - cut_value[l];
}

void dnc(int k,int l,int r,int x,int y) {
  if(l>r) return;
  int mid = x+y>>1;
  int v;
  for(int i=min(y,mid);i>=x;--i) {
    //
  }
  dnc(k,l,mid,x,v),
  dnc(k,mid+1,r,v,y);
}

int seg[N*4],lazy[N*4];

void init(int k,int pos,int l,int r) {
  lazy[pos] = 0;
  if(l==r) {
    seg[pos] = dp[k-1][l];
    return;
  }
  int mid = l+r>>1;
  init(k,pos*2,l,mid),
  init(k,pos*2+1,mid+1,r);
  seg[pos] = min(seg[pos*2],seg[pos*2+1]);
}

void push(int pos,int l,int r) {
  if(lazy[pos]!=0) {
    seg[pos] += lazy[pos];
    if(l!=r) {
      lazy[pos*2] += lazy[pos];
      lazy[pos*2+1] += lazy[pos];
    }
    lazy[pos] = 0;
  }
}

void update(int pos,int l,int r,int ql,int qr,int val) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return;
  }
  if(ql<=l && r<=qr) {
    lazy[pos] = val;
    push(pos,l,r);
    return;
  }
  int mid = (l+r)/2;
  update(pos*2,l,mid,ql,qr,val);
  update(pos*2+1,mid+1,r,ql,qr,val);
  seg[pos] = min(seg[pos*2],seg[pos*2+1]);
}
int query(int pos,int l,int r,int ql,int qr) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return 1e9;
  }
  if(ql<=l && r<=qr) {
    return seg[pos];
  }
  int mid = (l+r)/2;
  return min(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
}


void solve2() {
  int n,k;
  scanf("%d %d ", &n,&k);

  for(int i=1;i<=n;++i) {
    scanf("%d ", &a[i]);
  }

  int value = 0;
  for(int i=1;i<=n;++i) {
    if(color[a[i]]) {
      value += i - color[a[i]];
    }
    color[a[i]] = i;
    dp[1][i] = value;
  }
  for(int i=k;i;--i) dp[i][0] = 1e9;

  for(int i=2;i<=k;++i) {
    init(i,1,0,n);
    for(int j=1;j<=n;++j) color[j] = 0;
    for(int j=1;j<=n;++j) {
      if(color[a[j]]) {
        update(1,0,n,0,color[a[j]]-1, j-color[a[j]]);
      }
      color[a[j]] = j;
      dp[i][j] = query(1,0,n,0,j-1);
    }
  }

  printf("%d\n", dp[k][n]);
}

void solve() {
    // int t;
    // scanf("%d",&t);
    // while(t--)
    solve2();
}

inline bool exists_test0 (const std::string& name);
inline bool exists_test1 (const std::string& name);
int main() {
#ifdef LOCAL
  string file_name = "input.txt";
  assert(exists_test0(file_name));
  assert(exists_test1(file_name));
  freopen("input.txt","r",stdin);
#endif
  solve();
  return 0;
}

/*
0. Enough array size? Enough array size? Integer overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?

4. Be careful to use wrong variable.
*/
inline bool exists_test0 (const std::string& name) {
    ifstream f(name.c_str());
    return f.good();
}

inline bool exists_test1 (const std::string& name) {
    if (FILE *file = fopen(name.c_str(), "r")) {
        fclose(file);
        return true;
    } else {
        return false;
    }
}

### Prompt

Construct a cpp code solution to the problem outlined:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 35005;
const int K = 101;

int a[N];

int dp[K][N];

int color[N],d[N];
int cut_value[N];

int get_cost(int l,int r) {
  assert(l<=r);
  return dp[1][r] - dp[1][l-1] - cut_value[l];
}

void dnc(int k,int l,int r,int x,int y) {
  if(l>r) return;
  int mid = x+y>>1;
  int v;
  for(int i=min(y,mid);i>=x;--i) {
    //
  }
  dnc(k,l,mid,x,v),
  dnc(k,mid+1,r,v,y);
}

int seg[N*4],lazy[N*4];

void init(int k,int pos,int l,int r) {
  lazy[pos] = 0;
  if(l==r) {
    seg[pos] = dp[k-1][l];
    return;
  }
  int mid = l+r>>1;
  init(k,pos*2,l,mid),
  init(k,pos*2+1,mid+1,r);
  seg[pos] = min(seg[pos*2],seg[pos*2+1]);
}

void push(int pos,int l,int r) {
  if(lazy[pos]!=0) {
    seg[pos] += lazy[pos];
    if(l!=r) {
      lazy[pos*2] += lazy[pos];
      lazy[pos*2+1] += lazy[pos];
    }
    lazy[pos] = 0;
  }
}

void update(int pos,int l,int r,int ql,int qr,int val) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return;
  }
  if(ql<=l && r<=qr) {
    lazy[pos] = val;
    push(pos,l,r);
    return;
  }
  int mid = (l+r)/2;
  update(pos*2,l,mid,ql,qr,val);
  update(pos*2+1,mid+1,r,ql,qr,val);
  seg[pos] = min(seg[pos*2],seg[pos*2+1]);
}
int query(int pos,int l,int r,int ql,int qr) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return 1e9;
  }
  if(ql<=l && r<=qr) {
    return seg[pos];
  }
  int mid = (l+r)/2;
  return min(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
}


void solve2() {
  int n,k;
  scanf("%d %d ", &n,&k);

  for(int i=1;i<=n;++i) {
    scanf("%d ", &a[i]);
  }

  int value = 0;
  for(int i=1;i<=n;++i) {
    if(color[a[i]]) {
      value += i - color[a[i]];
    }
    color[a[i]] = i;
    dp[1][i] = value;
  }
  for(int i=k;i;--i) dp[i][0] = 1e9;

  for(int i=2;i<=k;++i) {
    init(i,1,0,n);
    for(int j=1;j<=n;++j) color[j] = 0;
    for(int j=1;j<=n;++j) {
      if(color[a[j]]) {
        update(1,0,n,0,color[a[j]]-1, j-color[a[j]]);
      }
      color[a[j]] = j;
      dp[i][j] = query(1,0,n,0,j-1);
    }
  }

  printf("%d\n", dp[k][n]);
}

void solve() {
    // int t;
    // scanf("%d",&t);
    // while(t--)
    solve2();
}

inline bool exists_test0 (const std::string& name);
inline bool exists_test1 (const std::string& name);
int main() {
#ifdef LOCAL
  string file_name = "input.txt";
  assert(exists_test0(file_name));
  assert(exists_test1(file_name));
  freopen("input.txt","r",stdin);
#endif
  solve();
  return 0;
}

/*
0. Enough array size? Enough array size? Integer overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?

4. Be careful to use wrong variable.
*/
inline bool exists_test0 (const std::string& name) {
    ifstream f(name.c_str());
    return f.good();
}

inline bool exists_test1 (const std::string& name) {
    if (FILE *file = fopen(name.c_str(), "r")) {
        fclose(file);
        return true;
    } else {
        return false;
    }
}

```