#include <bits/stdc++.h>
int a[500010], c[500010], f[500010], px[5010];
void modify(int s, int dt) {
  while (s <= 500) {
    c[s] = (c[s] > dt ? c[s] : dt);
    s += s & (-s);
  }
}
int fdlda(int s) {
  int snret = 0;
  snret = 0;
  while (s) {
    snret = (snret > c[s] ? snret : c[s]);
    s -= s & (-s);
  }
  return snret;
}
int main() {
  int n, t;
  n = 0;
  t = 0;
  scanf("%d%d", &n, &t);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 1; j <= 3000; j++) {
      a[i + j * n] = a[i];
    }
  }
  f[1] = 1;
  f[1] = 1;
  modify(a[1], 1);
  for (int i = 2; i <= 3000 * n; i++) {
    f[i] = fdlda(a[i]) + 1;
    modify(a[i], f[i]);
  }
  for (int i = 1; i <= 3000; i++) {
    px[i] = px[i - 1];
    px[i] = px[i - 1];
    for (int j = (i - 1) * n + 1; j <= i * n; j++) {
      px[i] = (px[i] > f[j] ? px[i] : f[j]);
    }
  }
  if (t <= 3000) {
    printf("%d\n", px[t]);
  } else {
    printf("%d\n", px[3000] + (px[3000] - px[2999]) * (t - 3000));
  }
}

### Prompt

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

You are given an array of positive integers a1, a2, ..., an × T of length n × T. We know that for any i > n it is true that ai = ai - n. Find the length of the longest non-decreasing sequence of the given array.

Input

The first line contains two space-separated integers: n, T (1 ≤ n ≤ 100, 1 ≤ T ≤ 107). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 300).

Output

Print a single number — the length of a sought sequence.

Examples

Input

4 3
3 1 4 2


Output

5

Note

The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence. 

### Response

```cpp
#include <bits/stdc++.h>
int a[500010], c[500010], f[500010], px[5010];
void modify(int s, int dt) {
  while (s <= 500) {
    c[s] = (c[s] > dt ? c[s] : dt);
    s += s & (-s);
  }
}
int fdlda(int s) {
  int snret = 0;
  snret = 0;
  while (s) {
    snret = (snret > c[s] ? snret : c[s]);
    s -= s & (-s);
  }
  return snret;
}
int main() {
  int n, t;
  n = 0;
  t = 0;
  scanf("%d%d", &n, &t);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 1; j <= 3000; j++) {
      a[i + j * n] = a[i];
    }
  }
  f[1] = 1;
  f[1] = 1;
  modify(a[1], 1);
  for (int i = 2; i <= 3000 * n; i++) {
    f[i] = fdlda(a[i]) + 1;
    modify(a[i], f[i]);
  }
  for (int i = 1; i <= 3000; i++) {
    px[i] = px[i - 1];
    px[i] = px[i - 1];
    for (int j = (i - 1) * n + 1; j <= i * n; j++) {
      px[i] = (px[i] > f[j] ? px[i] : f[j]);
    }
  }
  if (t <= 3000) {
    printf("%d\n", px[t]);
  } else {
    printf("%d\n", px[3000] + (px[3000] - px[2999]) * (t - 3000));
  }
}

```