#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long N = 1 << 17;
struct segtree {
  vector<long long> sum;
  void init() { sum.assign(2 * N, 0); }
  void upd(int pos, long long val, int node, int lx, int rx) {
    if (rx - lx == 1) {
      sum[node] = val;
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos < mid)
      upd(pos, val, 2 * node, lx, mid);
    else
      upd(pos, val, 2 * node + 1, mid, rx);
    sum[node] = sum[2 * node] + sum[2 * node + 1];
    return;
  }
  long long query(int l, int r, int node, int lx, int rx) {
    if (lx >= r || l >= rx) return 0;
    if (l <= lx && rx <= r) return sum[node];
    int mid = (lx + rx) / 2;
    long long a = query(l, r, 2 * node, lx, mid);
    long long b = query(l, r, 2 * node + 1, mid, rx);
    sum[node] = sum[2 * node] + sum[2 * node + 1];
    return a + b;
  }
};
void solve() {
  segtree st[15];
  for (int i = 0; i <= 14; i++) st[i].init();
  cin >> n >> k;
  long long fans = 0;
  for (int i = 1; i <= n; i++) {
    long long currval;
    cin >> currval;
    for (int curk = k + 1; curk >= 2; curk--) {
      long long ans = st[curk - 1].query(1, currval, 1, 0, N);
      if (curk == k + 1) fans += ans;
      st[curk].upd(currval, ans, 1, 0, N);
    }
    if (k == 0) fans += 1;
    st[1].upd(currval, 1, 1, 0, N);
  }
  cout << fans << endl;
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tc = 1;
  for (int i = 1; i <= tc; i++) {
    solve();
  }
  return 0;
}
