Problem: ICPC World Finals Day 6

Russian Constructivism is an art movement in the Soviet Union that began in the mid-1910s. Inspired by such things, Tee, who had been in Country R for a long time, decided to create a cool design despite the rehearsal of the ICPC World Finals. Mr. Tee says: "A circle and a line segment are enough for the symbol. It is important how beautifully the line segments intersect."

problem

Assign \\ (n \\) coordinates \\ (1, 2,…, n \\) to the circumference at equal intervals. There is exactly one line segment from each coordinate, and the line segment of the coordinate \\ (i \\) is connected to a different coordinate \\ (a_ {i} \\). (Conversely, the line segment of the coordinate \\ (a_ {i} \\) is connected to the coordinate \\ (a_ {a_ {i}} = i \\).) From this state, at most \\ (k) \\) You can reconnect the line segments of a book (freely regardless of coordinates and length) on the circumference. Answer the maximum size of a set of line segments that intersect each other.

input


n k
a1 a2… an


The number of coordinates \\ (n \\) and the number of line segments that can be reconnected \\ (k \\) are given on the first line, separated by blanks. On the second line, \\ (a_ {i} \\) representing the coordinates connecting the line segments of the coordinates \\ (i \\) is given, separated by blanks.

output

At most \\ (k \\) After reconnecting the line segments, output the maximum size of the set of line segments that intersect each other on one line.

Constraint

* \\ (2 \ leq n \ leq 8000 \\)
* \\ (n \\) is an even number
* \\ (0 \ leq k \ leq \ min (n / 2, 20) \\)
* \\ (1 \ leq a_ {i} \ leq n \\)
* \\ (a_ {i} \ not = i \\)
* Never connect a line segment to yourself
* \\ (a_ {i} \ not = a_ {j} (i \ not = j) \\)
* No more than one line segment can be connected at the same coordinates
* \\ (a_ {a_ {i}} = i \\)
* If a line segment is connected from \\ (i \\) to \\ (j \\), a line segment is connected from \\ (j \\) to \\ (i \\)



Input / output example

Input 1


8 0
7 4 6 2 8 3 1 5


Output 1


2


The line segments that intersect each other are represented by the red line segments in the figure below.

http://k-operafan.info/static/uecpc2013/files/art_sample_1.png

Input 2


8 1
7 4 6 2 8 3 1 5


Output 2


3


By reconnecting the line segments connecting 1 and 7 as shown in the figure below, three line segments that intersect each other can be obtained.

http://k-operafan.info/static/uecpc2013/files/art_sample_2.png

Input 3


8 0
5 6 7 8 1 2 3 4


Output 3


Four


Since all line segments intersect each other, the maximum number of intersecting line segments is four.

http://k-operafan.info/static/uecpc2013/files/art_sample_3.png





Example

Input

n k
a


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using ll = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b)a=b;};


template<typename T>
struct SegmentTree{
  using F = function<T(T, T)>;
  Int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){}
  SegmentTree(F f, T ti):f(f), ti(ti){}

  void init(Int n_){
    n = 1;
    while(n < n_) n<<= 1;
    dat.assign(n<<1, ti);
  }

  void build(const vector<T> &v){
    Int n_ = v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i] = v[i];
    for(Int i=n-1;i;i--)
      dat[i] = f(dat[(i<<1)|0], dat[(i<<1)|1]);
  }

  void set_val(Int k, T x){
    dat[k+=n] = x;
    while(k>>=1)
      dat[k] = f(dat[(k<<1) | 0], dat[(k<<1) | 1]);
  }

  T query(Int a,Int b){
    T vl = ti, vr = ti;
    for(Int l=a + n, r = b + n; l<r ; l>>=1, r>>=1){
      if(l&1) vl = f(vl, dat[l++]);
      if(r&1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
    

};
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);


  Int n,k;
  cin>>n>>k;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i],as[i]--;

  Int ans=1;
  for(Int i=0;i<n;i++){
    if(i>as[i]) continue;
    auto f=[](Int a,Int b){return max(a,b);};   
    SegmentTree<Int> seg(f,-n);
    seg.build(vector<Int>(n,-n));
    seg.set_val(as[i],1);
    for(Int j=i+1;j<as[i];j++){
      if(j>as[j]) continue;
      if(as[j]<as[i]) continue;      
      Int res=seg.query(0,as[j]);
      seg.set_val(as[j],res+1);
      //cout<<i<<" "<<j<<":"<<res+1<<endl;
      chmax(ans,res+1);
    }
  }
  
  ans+=k;
  chmin(ans,n/2);
  cout<<ans<<endl;
  return 0;
}