#include <bits/stdc++.h>
using namespace std;
long long num[100010];
long long dp[400010][50];
long long b[100010];
int n, m;
long long sum(long long x, long long y) {
  long long ret = 0;
  while (x > 0) {
    ret = (ret + dp[x][y]);
    x -= ((x) & -(x));
  }
  return ret;
}
void add(long long x, long long y, long long d) {
  while (x <= n) {
    dp[x][y] = (dp[x][y] + d);
    x += ((x) & -(x));
  }
}
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    m += 1;
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &num[i]);
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= min(i + 1, m); j++) {
        if (j == 1)
          add(num[i], 1, 1);
        else {
          long long temp = sum(num[i] - 1, j - 1);
          add(num[i], j, temp);
        }
      }
    }
    printf("%lld\n", sum(n, m));
  }
  return 0;
}
