#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxk = 15;
int n, k;
int a[maxn];
long long dp[maxk][maxn], c[maxn];
inline int read() {
  int res = 0, flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      flag = -1;
    }
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    res = res * 10 + ch - '0';
    ch = getchar();
  }
  return res * flag;
}
int lowbit(int x) { return x & (-x); }
void update(int p, long long w) {
  for (int i = p; i <= n; i += lowbit(i)) {
    c[i] += w;
  }
}
long long query(int p) {
  long long sum = 0;
  for (int i = p; i; i -= lowbit(i)) {
    sum += c[i];
  }
  return sum;
}
int main() {
  long long ans = 0;
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    dp[1][i] = 1;
  }
  for (int i = 2; i <= k + 1; i++) {
    for (int j = 1; j <= n; j++) {
      if (j >= i) {
        dp[i][j] = query(a[j] - 1);
      }
      update(a[j], dp[i - 1][j]);
    }
    for (int j = 1; j <= n; j++) {
      update(a[j], -dp[i - 1][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    ans += dp[k + 1][i];
  }
  printf("%lld\n", ans);
  return 0;
}
