#include <bits/stdc++.h>
using namespace std;
const int N = 300;
int dp[2][10010];
int a[10010];
int num[303];
int mx[310 << 2];
void update(int pos, int d, int l, int r, int rt) {
  if (l == r) {
    mx[rt] = d;
    return;
  }
  int m = l + r >> 1;
  if (pos <= m)
    update(pos, d, l, m, rt << 1);
  else
    update(pos, d, m + 1, r, rt << 1 | 1);
  mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
int query(int L, int R, int l, int r, int rt) {
  if (R < L) return 0;
  if (L <= l && R >= r) return mx[rt];
  int m = l + r >> 1;
  int s = 0;
  if (L <= m) s = query(L, R, l, m, rt << 1);
  if (R > m) s = max(s, query(L, R, m + 1, r, rt << 1 | 1));
  return s;
}
int main() {
  int i, j, k, m, n;
  int t;
  while (scanf("%d %d", &n, &t) == 2) {
    memset(num, 0, sizeof(num));
    for (i = 1; i <= n; i++) scanf("%d", a + i), num[a[i]]++;
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= min(n, t) - 1; i++)
      for (j = 1; j <= n; j++) a[i * n + j] = a[j];
    int left = t - min(n, t);
    n = n * min(n, t);
    memset(mx, 0, sizeof(mx));
    for (i = 1; i <= n; i++) {
      dp[0][i] = query(1, a[i], 1, N, 1) + 1;
      update(a[i], dp[0][i], 1, N, 1);
    }
    memset(mx, 0, sizeof(mx));
    for (i = n; i >= 1; i--) {
      dp[1][i] = query(a[i], N, 1, N, 1) + 1;
      update(a[i], dp[1][i], 1, N, 1);
    }
    int ans = 0;
    for (i = 1; i <= n; i++) {
      ans = max(ans, dp[0][i] + dp[1][i] - 1 + num[a[i]] * left);
    }
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Generate 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>
using namespace std;
const int N = 300;
int dp[2][10010];
int a[10010];
int num[303];
int mx[310 << 2];
void update(int pos, int d, int l, int r, int rt) {
  if (l == r) {
    mx[rt] = d;
    return;
  }
  int m = l + r >> 1;
  if (pos <= m)
    update(pos, d, l, m, rt << 1);
  else
    update(pos, d, m + 1, r, rt << 1 | 1);
  mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
int query(int L, int R, int l, int r, int rt) {
  if (R < L) return 0;
  if (L <= l && R >= r) return mx[rt];
  int m = l + r >> 1;
  int s = 0;
  if (L <= m) s = query(L, R, l, m, rt << 1);
  if (R > m) s = max(s, query(L, R, m + 1, r, rt << 1 | 1));
  return s;
}
int main() {
  int i, j, k, m, n;
  int t;
  while (scanf("%d %d", &n, &t) == 2) {
    memset(num, 0, sizeof(num));
    for (i = 1; i <= n; i++) scanf("%d", a + i), num[a[i]]++;
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= min(n, t) - 1; i++)
      for (j = 1; j <= n; j++) a[i * n + j] = a[j];
    int left = t - min(n, t);
    n = n * min(n, t);
    memset(mx, 0, sizeof(mx));
    for (i = 1; i <= n; i++) {
      dp[0][i] = query(1, a[i], 1, N, 1) + 1;
      update(a[i], dp[0][i], 1, N, 1);
    }
    memset(mx, 0, sizeof(mx));
    for (i = n; i >= 1; i--) {
      dp[1][i] = query(a[i], N, 1, N, 1) + 1;
      update(a[i], dp[1][i], 1, N, 1);
    }
    int ans = 0;
    for (i = 1; i <= n; i++) {
      ans = max(ans, dp[0][i] + dp[1][i] - 1 + num[a[i]] * left);
    }
    printf("%d\n", ans);
  }
  return 0;
}

```