#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int i, i0, n, m, k, a[100005];
long long tree[maxn * 4][12];
long long t[12];
void c_tree(int l, int r, int p, int a) {
  for (int i = 0; i <= k; i++) tree[p][i] += t[i];
  if (l != r) {
    if (a <= (l + r) / 2)
      c_tree(l, (l + r) / 2, p * 2, a);
    else if (a >= (l + r) / 2 + 1)
      c_tree((l + r) / 2 + 1, r, p * 2 + 1, a);
  }
}
void q_tree(int l, int r, int p, int a, int b) {
  if (l == a && r == b)
    for (int i = 0; i <= k; i++) t[i + 1] += tree[p][i];
  else {
    if (b <= (l + r) / 2)
      q_tree(l, (l + r) / 2, p * 2, a, b);
    else if (a >= (l + r) / 2 + 1)
      q_tree((l + r) / 2 + 1, r, p * 2 + 1, a, b);
    else
      q_tree(l, (l + r) / 2, p * 2, a, (l + r) / 2),
          q_tree((l + r) / 2 + 1, r, p * 2 + 1, (l + r) / 2 + 1, b);
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  t[0] = 1;
  c_tree(0, n, 1, 0);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    memset(t, 0, sizeof(t));
    q_tree(0, n, 1, 0, a[i]);
    ans += t[k + 1];
    c_tree(0, n, 1, a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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>
using namespace std;
const int maxn = 100005;
int i, i0, n, m, k, a[100005];
long long tree[maxn * 4][12];
long long t[12];
void c_tree(int l, int r, int p, int a) {
  for (int i = 0; i <= k; i++) tree[p][i] += t[i];
  if (l != r) {
    if (a <= (l + r) / 2)
      c_tree(l, (l + r) / 2, p * 2, a);
    else if (a >= (l + r) / 2 + 1)
      c_tree((l + r) / 2 + 1, r, p * 2 + 1, a);
  }
}
void q_tree(int l, int r, int p, int a, int b) {
  if (l == a && r == b)
    for (int i = 0; i <= k; i++) t[i + 1] += tree[p][i];
  else {
    if (b <= (l + r) / 2)
      q_tree(l, (l + r) / 2, p * 2, a, b);
    else if (a >= (l + r) / 2 + 1)
      q_tree((l + r) / 2 + 1, r, p * 2 + 1, a, b);
    else
      q_tree(l, (l + r) / 2, p * 2, a, (l + r) / 2),
          q_tree((l + r) / 2 + 1, r, p * 2 + 1, (l + r) / 2 + 1, b);
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  t[0] = 1;
  c_tree(0, n, 1, 0);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    memset(t, 0, sizeof(t));
    q_tree(0, n, 1, 0, a[i]);
    ans += t[k + 1];
    c_tree(0, n, 1, a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}

```