#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000 + 7;
const double esp = 1e-13;
int n, k, a[100000 + 10];
long long f[100000 + 10][20], l[100000 + 10][20], ans;
void update(int x, int v, long long value) {
  while (x <= n) {
    l[x][v] += value;
    x += x & (-x);
  }
}
long long get(int x, int v) {
  long long ans = 0;
  while (x) {
    ans += l[x][v];
    x -= x & (-x);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cin >> n >> k;
  k++;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) f[i][1] = 1;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= k; j++) {
      if (j > a[i]) f[i][j] = 0;
      if (j > 1) f[i][j] = get(a[i] - 1, j - 1);
      update(a[i], j, f[i][j]);
    }
  ans = 0;
  for (long long i = 1; i <= n; i++) ans += f[i][k];
  cout << ans;
}
