***C. Subsequences

C. Subsequences

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Examples

input

5 2
1
2
3
5
4

output

7

---------------------------------------------------EDITORIAL---------------------------------------------------

//SIMILAR QUESTION   first see this question

//http://gautamsegtree.blogspot.in/2016/02/d-babaei-and-birthday-cake.html

now 

THIS PROBLEM CAN BE SOLVED WITH SEG TREE + DP , 

 CONCEPT 

ITERATE FROM THE ARRAY AND FOR EACH ELEMENT i  

FIND NO OF WAYS OF PLACING THAT NUMBER AT  PACE J (FOR J ROM 1 TO K ) IN THE SEQUENCE WHICH WE WILL  CREATE ,

OBSERVATION ---

FOR PROCESSING NUMBER ARR[I] WE NEED TO COMPUTED ANSWER FOR ALL ARR[J] <ARR[I] AND J<I    BUT ANY ARR[J] >ARR[I] NEED NOT TO COMPUTED FOR PLACING iTH VALUE SO WE CAN SORT THE ARRAY WITH THE  VALUE AND KEEP INDEX OF EACH NUMBER ALSO ..

NOW SUPPOSE WE ARE TRYING TO PLACE iTH NUMBED AT jTH ( j CAN BE 1 TO K )PLACE  OF OUR SEQUENCE THAN WE JUST NEED THE SUM OF ALL POSSIBLE WAY IN WHICH WE CAN PLACE TILL ELEMENTS idx-1 (where idx-1 is the original index of the element arr[i])  AT POSITION j-1  THIS CAN BE COMPUTE USING A RANGE SUM QUERY , 

RANGE SUM QUERY WILL BE DONE  FROM INDEX 0 TO INDEX OF CURRENT NUMBER (actual index in the initial array ) 

WHILE UPDATING SEGMENT TREE  WE HAVE TO UPDATE ITS ANSWER AT INDEX idx (actual index of this number )

SEE IMPLEMENTATION 

------------------------------------------code------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int  lli;

lli arr[600000];

vector<pair<lli,lli> > v;

lli seg[600000][12];

lli dp[600000][12];

void update(int idx,int start,int end,int ups,int upe,int didx,lli val)

 {

  if(start>end || upe<start || ups>end) return ;

  else if(start==end && start==ups)

    {

      seg[idx][didx]=val;

      return ;

  }

  int mid=(start+end)/2;

  update(2*idx,start,mid,ups,ups,didx,val);

  update(2*idx+1,mid+1,end,ups,upe,didx,val);

  seg[idx][didx]=seg[2*idx][didx]+seg[2*idx+1][didx];

 }

 lli  qry(int idx,int start,int end,int qs,int qe,int didx)

 {

  if(start>end || qe<start || qs>end) return 0 ;

  else if(start>=qs && end<=qe)

    {

      return seg[idx][didx];

  }

  int mid=(start+end)/2;

 lli q1= qry(2*idx,start,mid,qs,qe,didx);

 lli q2= qry(2*idx+1,mid+1,end,qs,qe,didx);

   return (q1+q2);

 }

int main()

 {

  int n,k;

   cin>>n>>k;

   for(int i=0;i<n;i++)

     {

     int a; cin>>a;

     v.push_back({a,i});

  }

  sort(v.begin(),v.end());

   

  for(int i=0;i<n;i++)

   {

         int num=v[i].first;

           int idx=v[i].second;

           update(1,0,n-1,idx,idx,1,1);

           dp[i][1]=1;

           //cout<<" query is "<<num<<" idx "<<idx<<endl;

     for(int j=2;j<=k+1;j++)

         {

            //cout<<"placing "<<num<<" at  place "<<j<<" count "<<count<<endl;

    lli count=qry(1,0,n-1,0,idx-1,j-1);

    dp[i][j]=count;

    

    update(1,0,n-1,idx,idx,j,count);   

 }

   }

   

     lli ans=0;

     for(int i=0;i<n;i++)

      {

        ans+=dp[i][k+1];

 }

  cout<<ans<<endl;

 }