#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
long long n, m, i, j, k, l, s, t, d, ii, jj, x, y, z, h[N], hh[N][20],
    first[4 * N][11];
void u(int x, long long z, int y, int root, int bas, int son) {
  if (x < bas or x > son) return;
  first[root][y] += z;
  if (bas == son) return;
  u(x, z, y, (root + root), bas, ((bas + son) / 2));
  u(x, z, y, (root + root + 1), ((bas + son) / 2) + 1, son);
}
long long f(int x, int y, int z, int root, int bas, int son) {
  if (y < bas or x > son or x > y) return 0;
  if (x <= bas and y >= son) return first[root][z];
  return f(x, y, z, (root + root), bas, ((bas + son) / 2)) +
         f(x, y, z, (root + root + 1), ((bas + son) / 2) + 1, son);
}
int main() {
  cin >> n >> k;
  for (i = 1; i <= n; i++) scanf("%lld", h + i);
  for (i = n + 1; --i;) {
    u(h[i], 1, 1, 1, 1, n);
    for (j = 2; j <= k + 1; j++)
      u(h[i], f(h[i] + 1, n, j - 1, 1, 1, n), j, 1, 1, n);
  }
  cout << first[1][k + 1] << '\n';
}
