#include <bits/stdc++.h>
using namespace std;
double esp = 1e-12;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const long long int MOD = 1000000007;
int m[110];
int so[310];
int sum[310];
int main() {
  int n, t;
  memset(m, 0, sizeof(m));
  memset(sum, 0, sizeof(sum));
  scanf("%d%d", &n, &t);
  for (int x = 0; x < n; x++) {
    scanf("%d", &m[x]);
    sum[m[x]]++;
  }
  memset(so, 0, sizeof(so));
  if (t <= n) {
    for (int x = 0; x < t * n; x++) {
      so[m[x % n]]++;
      for (int y = 1; y < m[x % n]; y++)
        so[m[x % n]] = max(so[m[x % n]], so[y] + 1);
    }
    int ans = 0;
    for (int x = 1; x <= 300; x++) ans = max(ans, so[x]);
    printf("%d\n", ans);
  } else {
    for (int x = 0; x < n * n; x++) {
      so[m[x % n]]++;
      for (int y = 1; y < m[x % n]; y++)
        so[m[x % n]] = max(so[m[x % n]], so[y] + 1);
    }
    long long int ans = 0, ans1 = 0;
    for (int x = 1; x <= 300; x++) ans = max(ans, (long long int)so[x]);
    for (int x = 1; x <= 300; x++) ans1 = max(ans1, (long long int)sum[x]);
    printf("%I64d\n", ans + (t - n) * ans1);
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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>
using namespace std;
double esp = 1e-12;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const long long int MOD = 1000000007;
int m[110];
int so[310];
int sum[310];
int main() {
  int n, t;
  memset(m, 0, sizeof(m));
  memset(sum, 0, sizeof(sum));
  scanf("%d%d", &n, &t);
  for (int x = 0; x < n; x++) {
    scanf("%d", &m[x]);
    sum[m[x]]++;
  }
  memset(so, 0, sizeof(so));
  if (t <= n) {
    for (int x = 0; x < t * n; x++) {
      so[m[x % n]]++;
      for (int y = 1; y < m[x % n]; y++)
        so[m[x % n]] = max(so[m[x % n]], so[y] + 1);
    }
    int ans = 0;
    for (int x = 1; x <= 300; x++) ans = max(ans, so[x]);
    printf("%d\n", ans);
  } else {
    for (int x = 0; x < n * n; x++) {
      so[m[x % n]]++;
      for (int y = 1; y < m[x % n]; y++)
        so[m[x % n]] = max(so[m[x % n]], so[y] + 1);
    }
    long long int ans = 0, ans1 = 0;
    for (int x = 1; x <= 300; x++) ans = max(ans, (long long int)so[x]);
    for (int x = 1; x <= 300; x++) ans1 = max(ans1, (long long int)sum[x]);
    printf("%I64d\n", ans + (t - n) * ans1);
  }
  return 0;
}

```