#include <bits/stdc++.h>
//#define int long long int
#define ll long long int
#define ld long double
#define getFaster ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define rep(i, init, n) for (int i = init; i < (int)n; i++)
#define rev(i, n, init) for (int i = (int)n; i >= init; i--)
#define MOD1 1e9 + 7
#define MOD2 998244353
#define f first
#define s second
#define endl '\n'
#define pii pair<int, int>
#define tii tuple<int, int>
#define all(v) v.begin(), v.end()
#define mt make_tuple
#define precise(i) cout << fixed << setprecision(i)
#define codejam cout << "Case #" << ii + 1 << ": ";
#define impossible cout << "IMPOSSIBLE" << endl;
#define error(s) throw runtime_error(s)
#define hash hash1
#define data data1
#define prev prev1
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int myRand(int R)
{
     int val = rng() % R;
     assert(val >= 0);
     return val;
}

const long double PI = atan(1.0) * 4;
const int32_t INF32 = 2e9 + 7;
const int64_t INF64 = 3e18;
const int32_t LOG = 21;
int32_t MOD = MOD1;

using namespace std;

//-------------------DEBUGGING-------------------------
void my_debugger(string s, int LINE_NUM) { cerr << endl; }
template <typename start, typename... end>
void my_debugger(string s, int LINE_NUM, start x, end... y)
{
     if (s.back() != ',')
     {
          s += ',';
          cerr << "LINE(" << LINE_NUM << "): ";
     }
     int i = s.find(',');
     cerr << s.substr(0, i) << " = " << x;
     s = s.substr(i + 1);
     if (!s.empty())
          cerr << ", ";
     my_debugger(s, LINE_NUM, y...);
}

#ifdef AJIT
#define debug(...) my_debugger(#__VA_ARGS__, __LINE__, __VA_ARGS__);
#else
#define debug(...) ;
#endif

void setMod(int mod_val)
{
     MOD = mod_val;
}
//-----------------------------------------------------

void files_init()
{
     freopen("maxflow.in", "r", stdin);
     freopen("maxflow.out", "w", stdout);
}

const int N = 35001;
const int LOGN = 20;

vector<int> dp_before,dp_cur;
int a[N];
int prev[N];
int recent[N];
vector<int> vals[N];
int dp[N][(N/20)+2];

int cost(int l,int r)
{
     if(l>r)return 0;
     int len=(r-l+1);
     int ind=len/20;
     int ans=dp[l][ind];
     for(int j=l+20*ind;j<=r;j++)
     {
          if(prev[j]>=l)
          ans+=(j-prev[j]);
     }
     return ans;
}

void compute(int l, int r, int optl, int optr)
{
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {INF32, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {dp_before[k] + cost(k+1,mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;
  
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

void precompute(int n)
{
     iota(begin(prev),end(prev),0);
     fill(begin(recent),end(recent),-1);

     rep(i,0,n)
     {
          if(recent[a[i]]!=-1)
          prev[i]=recent[a[i]];
          recent[a[i]]=i;
     }

     
     rep(i,0,n)
     {
          int cur=0;
          int block=1;
          int val=0;
          rep(j,i,n)
          {
               if(prev[j]>=i)
               val+=(j-prev[j]);
               cur++;
               if(cur==20)
               {
                    dp[i][block]=val;
                    cur=0;
                    block++;
               }
          }
     }
}


int32_t main()
{
     getFaster;
     //files_init();
     int tests = 1;
     //cin >> tests;
     rep(ii, 0, tests)
     {
          int n,partitions;
          cin>>n>>partitions;
 
          rep(i,0,n)
          cin>>a[i];

          precompute(n);

          dp_before.resize(n);
          dp_cur.resize(n);

          rep(i,0,n)
          dp_before[i]=cost(0,i);

          rep(i,2,partitions+1)
          {
               compute(0,n-1,0,n-1);
               dp_before=dp_cur;
          }

          cout<<dp_before.back()<<endl;
     }
     return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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>
//#define int long long int
#define ll long long int
#define ld long double
#define getFaster ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define rep(i, init, n) for (int i = init; i < (int)n; i++)
#define rev(i, n, init) for (int i = (int)n; i >= init; i--)
#define MOD1 1e9 + 7
#define MOD2 998244353
#define f first
#define s second
#define endl '\n'
#define pii pair<int, int>
#define tii tuple<int, int>
#define all(v) v.begin(), v.end()
#define mt make_tuple
#define precise(i) cout << fixed << setprecision(i)
#define codejam cout << "Case #" << ii + 1 << ": ";
#define impossible cout << "IMPOSSIBLE" << endl;
#define error(s) throw runtime_error(s)
#define hash hash1
#define data data1
#define prev prev1
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int myRand(int R)
{
     int val = rng() % R;
     assert(val >= 0);
     return val;
}

const long double PI = atan(1.0) * 4;
const int32_t INF32 = 2e9 + 7;
const int64_t INF64 = 3e18;
const int32_t LOG = 21;
int32_t MOD = MOD1;

using namespace std;

//-------------------DEBUGGING-------------------------
void my_debugger(string s, int LINE_NUM) { cerr << endl; }
template <typename start, typename... end>
void my_debugger(string s, int LINE_NUM, start x, end... y)
{
     if (s.back() != ',')
     {
          s += ',';
          cerr << "LINE(" << LINE_NUM << "): ";
     }
     int i = s.find(',');
     cerr << s.substr(0, i) << " = " << x;
     s = s.substr(i + 1);
     if (!s.empty())
          cerr << ", ";
     my_debugger(s, LINE_NUM, y...);
}

#ifdef AJIT
#define debug(...) my_debugger(#__VA_ARGS__, __LINE__, __VA_ARGS__);
#else
#define debug(...) ;
#endif

void setMod(int mod_val)
{
     MOD = mod_val;
}
//-----------------------------------------------------

void files_init()
{
     freopen("maxflow.in", "r", stdin);
     freopen("maxflow.out", "w", stdout);
}

const int N = 35001;
const int LOGN = 20;

vector<int> dp_before,dp_cur;
int a[N];
int prev[N];
int recent[N];
vector<int> vals[N];
int dp[N][(N/20)+2];

int cost(int l,int r)
{
     if(l>r)return 0;
     int len=(r-l+1);
     int ind=len/20;
     int ans=dp[l][ind];
     for(int j=l+20*ind;j<=r;j++)
     {
          if(prev[j]>=l)
          ans+=(j-prev[j]);
     }
     return ans;
}

void compute(int l, int r, int optl, int optr)
{
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {INF32, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {dp_before[k] + cost(k+1,mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;
  
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

void precompute(int n)
{
     iota(begin(prev),end(prev),0);
     fill(begin(recent),end(recent),-1);

     rep(i,0,n)
     {
          if(recent[a[i]]!=-1)
          prev[i]=recent[a[i]];
          recent[a[i]]=i;
     }

     
     rep(i,0,n)
     {
          int cur=0;
          int block=1;
          int val=0;
          rep(j,i,n)
          {
               if(prev[j]>=i)
               val+=(j-prev[j]);
               cur++;
               if(cur==20)
               {
                    dp[i][block]=val;
                    cur=0;
                    block++;
               }
          }
     }
}


int32_t main()
{
     getFaster;
     //files_init();
     int tests = 1;
     //cin >> tests;
     rep(ii, 0, tests)
     {
          int n,partitions;
          cin>>n>>partitions;
 
          rep(i,0,n)
          cin>>a[i];

          precompute(n);

          dp_before.resize(n);
          dp_cur.resize(n);

          rep(i,0,n)
          dp_before[i]=cost(0,i);

          rep(i,2,partitions+1)
          {
               compute(0,n-1,0,n-1);
               dp_before=dp_cur;
          }

          cout<<dp_before.back()<<endl;
     }
     return 0;
}
```