#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back 
#define ll long long
#define SZ(a) ((int)(a.size()))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define mp make_pair

using namespace std;

// dp[i][j][k]//i为当前位置，j为第二大值，k为第二大的长度
// 当j>sufmin(i+1~n)时，为无效状态，可以利用该性质优化
// 所以有j<sufmin...，每次转移的时候，只有该值为sufmin的时候才可以转移到sec
// 
// dp[i][j][k]
const int N=5010;
const int inf=1e9;
int dp[N][N][N];
int a[N];
int premax[N],sufmin[N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    rep(i,1,n+1){
        premax[i]=max(premax[i-1],a[i]);
    }
    sufmin[n+1]=inf;
    for(int i=n;i>=1;i--){
        sufmin[i]=min(sufmin[i+1],a[i]);
    }
    // dp[i][j][k]
    // dp[i+1][j][k]=
    // if(a[i+1]==premax[i+1])  dp[i][j][k]- >dp[i+1][premax[i]][i+1-k]; /   dp[i+1][j][k];
    // if(a[i+1]>j)  dp[i][j][k]->dp[i+1][a[i+1]][k+1];
    dp[0][0][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=m;k++){
                if(i<k)continue;
                if(premax[i+1]==a[i+1]){
                    dp[i+1][premax[i]][i-k]+=dp[i][j][k];  //将a[i+1]放在j后面
                    dp[i+1][j][k]+=dp[i][j][k];
                     //将a[i+1]放在  最大序列后面
                }
                else if(a[i+1]>j){
                    
                    dp[i+1][a[i+1]][k+1]+=dp[i][j][k];
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++)
        if(n-i<=m)res+=dp[n][j][i];
    }
    cout<<res<<"\n";
}

/tmp/ccvbtv4f.o: In function `_GLOBAL__sub_I_dp':
answer.code:(.text.startup+0x9c4): relocation truncated to fit: R_X86_64_PC32 against `.bss'
collect2: error: ld returned 1 exit status