#include <bits/stdc++.h>
using namespace std;
void file() {}
const int N = 1e5 + 5, MAX = 3e7, MOD = 1e9 + 7;
int a[N];
int n, k;
long long dp[N][12];
long long seg[4 * N][12];
void update(int indx, int l, int r, int pos, int who, long long val) {
  if (l == r) {
    seg[indx][who] = val;
    return;
  }
  if (pos <= (l + r) / 2)
    update(indx * 2, l, (l + r) / 2, pos, who, val);
  else
    update(indx * 2 + 1, (l + r) / 2 + 1, r, pos, who, val);
  seg[indx][who] = seg[indx * 2][who] + seg[indx * 2 + 1][who];
}
long long get(int indx, int l, int r, int i, int j, int who) {
  if (l > j || r < i) return 0;
  if (l >= i && r <= j) return seg[indx][who];
  return get(indx * 2, l, (l + r) / 2, i, j, who) +
         get(indx * 2 + 1, (l + r) / 2 + 1, r, i, j, who);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  file();
  scanf("%d %d", &n, &k);
  k++;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 2; j <= k; j++) {
      dp[i][j] = get(1, 1, N - 1, a[i] + 1, N - 1, j - 1);
      if (j == k) dp[i][j] += dp[i + 1][j];
      update(1, 1, N - 1, a[i], j, dp[i][j]);
    }
    update(1, 1, N - 1, a[i], 1, 1);
    dp[i][1] = dp[i + 1][1] + 1;
  }
  printf("%lld\n", dp[0][k]);
}
