C. Subsequences

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Sample test(s)

input

5 2 1 2 3 5 4

output

7

#include
         
          #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=100100;const int INF=(1<<29);int n,k;ll a[maxn];ll c[maxn][15];int lowbit(int x){    return x&(-x);}ll sum(int p,int id){    ll res=0;    while(p>0){        res+=c[p][id];        p-=lowbit(p);    }    return res;}void add(int p,int id,ll x){    while(p<=n){        c[p][id]+=x;        p+=lowbit(p);    }}int main(){    ///freopen("in.txt","r",stdin);    while(cin>>n>>k){        REP(i,1,n) scanf("%I64d",&a[i]);        MS0(c);        REP(i,1,n){            add(a[i],1,1);            REP(j,2,k+1) add(a[i],j,sum(a[i]-1,j-1));        }        cout<
          
           <