#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, int>> val;
vector<vector<long long>> Tree;
vector<int> loc;
int k;
bool compare2(pair<long long, int> A, pair<long long, int> B) {
  return A.second < B.second;
}
int update(int loc, int l, int r, int v, vector<long long> NEW) {
  if (l == r && l == loc) {
    for (int i = 1; i < k + 1; i++) {
      Tree[v][i] = NEW[i] + Tree[v][i];
    }
    return 0;
  } else if (l > r || l > loc || r < loc) {
    return 0;
  } else {
    int mid = (l + r) >> 1;
    update(loc, l, mid, 2 * v, NEW);
    update(loc, mid + 1, r, 2 * v + 1, NEW);
    for (int i = 1; i < k + 1; i++) {
      Tree[v][i] = Tree[2 * v][i] + Tree[2 * v + 1][i];
    }
    return 0;
  }
}
long long find(int l, int r, int L, int R, int v, int A) {
  if (l == L && r == R) {
    return Tree[v][A];
  } else if (L > R || l > r || l > R || L > r) {
    return 0;
  } else {
    int mid = (L + R) >> 1;
    long long val1 = find(l, min(mid, r), L, mid, 2 * v, A);
    long long val2 = find(max(mid + 1, l), r, mid + 1, R, 2 * v + 1, A);
    return val1 + val2;
  }
}
int main() {
  int n;
  cin >> n >> k;
  k++;
  val.resize(n + 1);
  Tree.resize(4 * n + 3);
  long long a;
  for (int i = 0; i < 4 * n + 3; i++) {
    Tree[i].assign(k + 1, 0);
  }
  for (int i = 1; i < n + 1; i++) {
    cin >> a;
    val[i].first = a;
    val[i].second = i;
  }
  sort(val.begin() + 1, val.end());
  long long curr = 0;
  loc.assign(n + 1, 0);
  int nums = 0;
  for (int i = 1; i < n + 1; i++) {
    if (curr < val[i].first) {
      nums++;
      curr = val[i].first;
    }
    loc[val[i].second] = nums;
  }
  sort(val.begin() + 1, val.end(), compare2);
  vector<long long> temp;
  for (int i = 1; i < n + 1; i++) {
    temp.assign(k + 1, 0);
    for (int j = 1; j < k + 1; j++) {
      long long prev = find(1, loc[val[i].second] - 1, 1, n, 1, j - 1);
      temp[j] = prev;
      if (j == 1) {
        temp[j]++;
      }
    }
    update(loc[val[i].second], 1, n, 1, temp);
  }
  cout << Tree[1][k] << endl;
  return 0;
}
