#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int rt[maxn], cnt;
long long ans;
struct node {
  int l, r;
  long long val;
  node() {
    l = r = 0;
    val = 0;
  }
  node(int L, int R, long long V) : l(L), r(R), val(V) {}
} s[maxn * 40];
long long query(int Now, int L, int R, int l, int r) {
  if (l <= L && r >= R) return s[Now].val;
  long long res = 0;
  int Mid = (L + R) >> 1;
  if (l <= Mid) res += query(s[Now].l, L, Mid, l, r);
  if (r > Mid) res += query(s[Now].r, Mid + 1, R, l, r);
  return res;
}
void insert(int &Now, int pre, int L, int R, int pos, long long val) {
  Now = ++cnt;
  s[Now] = node(s[pre].l, s[pre].r, s[pre].val + val);
  if (L == R) return;
  int Mid = (L + R) >> 1;
  if (pos <= Mid)
    insert(s[Now].l, s[pre].l, L, Mid, pos, val);
  else
    insert(s[Now].r, s[pre].r, Mid + 1, R, pos, val);
}
void update(int &Now, int L, int R, int pos, long long val) {
  if (Now == 0) Now = ++cnt;
  s[Now].val += val;
  if (L == R) return;
  int Mid = (L + R) >> 1;
  if (pos <= Mid)
    update(s[Now].l, L, Mid, pos, val);
  else
    update(s[Now].r, Mid + 1, R, pos, val);
}
int main() {
  int N, K, i, j, x;
  scanf("%d%d", &N, &K);
  for (i = 1; i <= N; i++) {
    scanf("%d", &x);
    x += 2;
    update(rt[1], 1, N + 2, x, 1);
    for (j = 0; j <= K; j++) {
      long long tmp = query(rt[j], 1, N + 2, 1, x - 1);
      update(rt[j + 1], 1, N + 2, x, tmp);
    }
  }
  ans = query(rt[K + 1], 1, N + 2, 1, N + 2);
  printf("%I64d\n", ans);
  return 0;
}
