#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 3;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n;
int a[MAXN];
long long seg[12][4 * MAXN];
void add(int j, int l, int r, long long val, int b = 0, int e = n, int k = 0) {
  if (l <= b && e <= r) {
    seg[j][k] += val;
    return;
  }
  if (r <= b || e <= l) return;
  int mid = (b + e) / 2;
  add(j, l, r, val, b, mid, k * 2 + 1);
  add(j, l, r, val, mid, e, k * 2 + 2);
}
long long get(int j, int i, int b = 0, int e = n, int k = 0) {
  if (i < b || i >= e) return 0;
  if (b + 1 == e) return seg[j][k];
  int mid = (b + e) / 2;
  return seg[j][k] + get(j, i, b, mid, k * 2 + 1) +
         get(j, i, mid, e, k * 2 + 2);
}
int main() {
  cin >> n;
  int k;
  cin >> k;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    a[x] = i;
  }
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
      add(1, a[i], n, 1);
    } else {
      for (int j = 2; j <= k + 1; j++) {
        long long x = get(j - 1, a[i] - 1);
        add(j, a[i], n, x);
      }
      add(1, a[i], n, 1);
    }
  }
  cout << get(k + 1, n - 1);
  return 0;
}
