#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
const int md = 1000000007;
int n, T;
long long ans;
int d[555], e[555], p[555], a[555], cnt[555][555];
void read(int &x) {
  char ch = getchar();
  x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
int main() {
  scanf("%d%d", &n, &T);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i <= 301; i++)
    for (int j = 1; j <= n; j++) cnt[i][j] = cnt[i][j - 1] + (a[j] == i);
  for (int i = 1; i <= n; i++) d[i] = e[i] = 0;
  if (T <= 2 * n) {
    for (int st = 1; st <= T; st++) {
      for (int i = 1; i <= n; i++) p[i] = d[i];
      for (int i = 1; i <= n; i++)
        for (int j = -n + 1; j < i; j++) {
          int k, l;
          if (j <= 0)
            l = j + n;
          else
            l = j;
          if (j <= 0)
            k = p[j + n];
          else
            k = d[j];
          if (a[l] <= a[i] && k + 1 > d[i]) d[i] = k + 1;
        }
    }
    for (int i = 1; i <= n; i++) ans = max(ans, (long long)d[i]);
    cout << ans << endl;
    return 0;
  }
  for (int st = 1; st <= n; st++) {
    for (int i = 1; i <= n; i++) p[i] = d[i];
    for (int i = 1; i <= n; i++)
      for (int j = -n + 1; j < i; j++) {
        int k, l;
        if (j <= 0)
          l = j + n;
        else
          l = j;
        if (j <= 0)
          k = p[j + n];
        else
          k = d[j];
        if (a[l] <= a[i] && k + 1 > d[i]) d[i] = k + 1;
      }
  }
  for (int st = 1; st <= n; st++) {
    for (int i = 1; i <= n; i++) p[i] = e[i];
    for (int i = n; i >= 1; i--)
      for (int j = i + 1; j <= n + n; j++) {
        int k, l;
        if (j > n)
          l = j - n;
        else
          l = j;
        if (j > n)
          k = p[j - n];
        else
          k = e[j];
        if (a[l] >= a[i] && k + 1 > e[i]) e[i] = k + 1;
      }
  }
  for (int i = 1; i <= n; i++) {
    long long tmp = 0;
    for (int j = n; j >= 1; j--) {
      if (a[j] == a[i]) {
        tmp += d[j];
        break;
      }
    }
    for (int j = 1; j <= n; j++) {
      if (a[j] == a[i]) {
        tmp += e[j];
        break;
      }
    }
    tmp = tmp + (long long)(T - 2 * n) * cnt[a[i]][n];
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

### Prompt

Please formulate 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 inf = 1000000000;
const int md = 1000000007;
int n, T;
long long ans;
int d[555], e[555], p[555], a[555], cnt[555][555];
void read(int &x) {
  char ch = getchar();
  x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
int main() {
  scanf("%d%d", &n, &T);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i <= 301; i++)
    for (int j = 1; j <= n; j++) cnt[i][j] = cnt[i][j - 1] + (a[j] == i);
  for (int i = 1; i <= n; i++) d[i] = e[i] = 0;
  if (T <= 2 * n) {
    for (int st = 1; st <= T; st++) {
      for (int i = 1; i <= n; i++) p[i] = d[i];
      for (int i = 1; i <= n; i++)
        for (int j = -n + 1; j < i; j++) {
          int k, l;
          if (j <= 0)
            l = j + n;
          else
            l = j;
          if (j <= 0)
            k = p[j + n];
          else
            k = d[j];
          if (a[l] <= a[i] && k + 1 > d[i]) d[i] = k + 1;
        }
    }
    for (int i = 1; i <= n; i++) ans = max(ans, (long long)d[i]);
    cout << ans << endl;
    return 0;
  }
  for (int st = 1; st <= n; st++) {
    for (int i = 1; i <= n; i++) p[i] = d[i];
    for (int i = 1; i <= n; i++)
      for (int j = -n + 1; j < i; j++) {
        int k, l;
        if (j <= 0)
          l = j + n;
        else
          l = j;
        if (j <= 0)
          k = p[j + n];
        else
          k = d[j];
        if (a[l] <= a[i] && k + 1 > d[i]) d[i] = k + 1;
      }
  }
  for (int st = 1; st <= n; st++) {
    for (int i = 1; i <= n; i++) p[i] = e[i];
    for (int i = n; i >= 1; i--)
      for (int j = i + 1; j <= n + n; j++) {
        int k, l;
        if (j > n)
          l = j - n;
        else
          l = j;
        if (j > n)
          k = p[j - n];
        else
          k = e[j];
        if (a[l] >= a[i] && k + 1 > e[i]) e[i] = k + 1;
      }
  }
  for (int i = 1; i <= n; i++) {
    long long tmp = 0;
    for (int j = n; j >= 1; j--) {
      if (a[j] == a[i]) {
        tmp += d[j];
        break;
      }
    }
    for (int j = 1; j <= n; j++) {
      if (a[j] == a[i]) {
        tmp += e[j];
        break;
      }
    }
    tmp = tmp + (long long)(T - 2 * n) * cnt[a[i]][n];
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

```