#include <bits/stdc++.h>
const long long MOD = 998244353;
const long long INF = 1e9 + 7;
using namespace std;
inline long long read();
long long n, k;
long long a[200010], c[200010][20];
long long dp[200010][20];
long long lowbit(int x) { return x & (-x); }
void updata(int num, int i, long long k) {
  while (i < 200010) {
    c[i][num] += k;
    i += lowbit(i);
  }
}
long long presum(int num, int i) {
  long long res = 0;
  while (i) {
    res += c[i][num];
    i -= lowbit(i);
  }
  return res;
}
int main() {
  n = read();
  k = read();
  k++;
  for (int i = 1; i <= n; i++) a[i] = read();
  updata(0, 1, 1);
  for (int i = 1; i <= n; i++) {
    for (int j = k; j >= 1; j--) {
      dp[a[i]][j] += presum(j - 1, a[i]);
      updata(j, a[i], dp[a[i]][j]);
    }
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) ans += dp[i][k];
  cout << ans;
  return 0;
}
inline long long read() {
  long long nxt = 1, ans = 0;
  char ch = getchar();
  while (ch < 48 || ch > 57) {
    if (ch == '-') nxt = -1;
    ch = getchar();
  }
  while (ch >= 48 && ch <= 57) {
    ans = (ans << 3) + (ans << 1) + ch - 48;
    ch = getchar();
  }
  return ans * nxt;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Examples

Input

5 2
1
2
3
5
4


Output

7

### Response

```cpp
#include <bits/stdc++.h>
const long long MOD = 998244353;
const long long INF = 1e9 + 7;
using namespace std;
inline long long read();
long long n, k;
long long a[200010], c[200010][20];
long long dp[200010][20];
long long lowbit(int x) { return x & (-x); }
void updata(int num, int i, long long k) {
  while (i < 200010) {
    c[i][num] += k;
    i += lowbit(i);
  }
}
long long presum(int num, int i) {
  long long res = 0;
  while (i) {
    res += c[i][num];
    i -= lowbit(i);
  }
  return res;
}
int main() {
  n = read();
  k = read();
  k++;
  for (int i = 1; i <= n; i++) a[i] = read();
  updata(0, 1, 1);
  for (int i = 1; i <= n; i++) {
    for (int j = k; j >= 1; j--) {
      dp[a[i]][j] += presum(j - 1, a[i]);
      updata(j, a[i], dp[a[i]][j]);
    }
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) ans += dp[i][k];
  cout << ans;
  return 0;
}
inline long long read() {
  long long nxt = 1, ans = 0;
  char ch = getchar();
  while (ch < 48 || ch > 57) {
    if (ch == '-') nxt = -1;
    ch = getchar();
  }
  while (ch >= 48 && ch <= 57) {
    ans = (ans << 3) + (ans << 1) + ch - 48;
    ch = getchar();
  }
  return ans * nxt;
}

```