#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
long long int a[maxn], dp[maxn], pd[maxn];
long long int n, seg[4 * maxn];
void add(int idx, long long int val, int first = 0, int second = n,
         int id = 1) {
  if (first == second - 1) {
    seg[id] = val;
    return;
  }
  int mid = (first + second) >> 1;
  if (idx < mid)
    add(idx, val, first, mid, id * 2 + 0);
  else
    add(idx, val, mid, second, id * 2 + 1);
  seg[id] = seg[id * 2 + 0] + seg[id * 2 + 1];
}
long long int get(int l, int r, int first = 0, int second = n, int id = 1) {
  if (l == first && r == second) return seg[id];
  int mid = (first + second) >> 1;
  long long int sum = 0;
  if (l < mid) sum += get(l, min(r, mid), first, mid, id * 2 + 0);
  if (r > mid) sum += get(max(l, mid), r, mid, second, id * 2 + 1);
  return sum;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i], a[i]--, dp[i] = 1;
  if (k == 0) {
    cout << n << endl;
    return 0;
  }
  for (int rep = 1; rep <= k; rep++) {
    memset(seg, 0, sizeof seg);
    for (int i = 0; i < n; i++) {
      pd[i] = get(0, a[i] + 1);
      add(a[i], dp[i]);
    }
    for (int i = 0; i < n; i++) dp[i] = pd[i];
  }
  long long int ans = 0;
  for (int i = 0; i < n; i++) ans += pd[i];
  cout << ans << endl;
  return 0;
}
