#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
long long int BIT[16][N], suffix[N];
void upd(int x, int lv, long long int plus) {
  while (x < N) {
    BIT[lv][x] += plus;
    x += x & (-x);
  }
}
long long int query(int x, int lv) {
  long long int ans = 0LL;
  while (x > 0) {
    ans += BIT[lv][x];
    x -= x & (-x);
  }
  return ans;
}
long long int n, k, v[N], cnt[16][N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  memset(BIT, 0LL, sizeof(BIT));
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> v[i];
  for (int i = 1; i <= n; ++i) cnt[0][i] = 1LL;
  for (int i = n; i >= 1; --i) {
    int x = v[i];
    for (int j = 1; j <= k; ++j) {
      cnt[j][x] = query(n, j) - query(x, j);
      upd(x, j, cnt[j - 1][x]);
    }
  }
  long long int ans = 0LL;
  ans = 0LL;
  for (int i = 1; i <= n; ++i) ans += cnt[k][i];
  if (k == 0LL) ans = n;
  cout << ans << "\n";
}
