#include <bits/stdc++.h>
using namespace std;
void LIS(int lis[], int arr[], int n) {
  for (int i = 0; i < n; i++) lis[i] = 1;
  for (int i = 1; i < n; i++)
    for (int j = 0; j < i; j++)
      if (arr[i] >= arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1;
}
int main() {
  int n, t;
  cin >> n >> t;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t <= n) {
    int newarr[n * t];
    for (int j = 0; j < n * t; j++) {
      newarr[j] = a[j % n];
    }
    int dp[n * t];
    LIS(dp, newarr, n * t);
    int max = 0;
    for (int i = n * t - 1; i >= n * (t - 1); i--) {
      if (max < dp[i]) {
        max = dp[i];
      }
    }
    cout << max << endl;
  } else {
    int newarr[(n * n) + n];
    for (int j = 0; j < (n * n) + n; j++) {
      newarr[j] = a[j % n];
    }
    int dp[n * n + n];
    LIS(dp, newarr, (n * n) + n);
    int rem = t - (n + 1);
    int tempnew[n];
    for (int j = 0; j < n; j++) {
      tempnew[j] =
          dp[j + (n * n)] + rem * (dp[j + (n * n)] - dp[j + (n * n) - n]);
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
      if (max < tempnew[i]) {
        max = tempnew[i];
      }
    }
    cout << max << endl;
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
void LIS(int lis[], int arr[], int n) {
  for (int i = 0; i < n; i++) lis[i] = 1;
  for (int i = 1; i < n; i++)
    for (int j = 0; j < i; j++)
      if (arr[i] >= arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1;
}
int main() {
  int n, t;
  cin >> n >> t;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t <= n) {
    int newarr[n * t];
    for (int j = 0; j < n * t; j++) {
      newarr[j] = a[j % n];
    }
    int dp[n * t];
    LIS(dp, newarr, n * t);
    int max = 0;
    for (int i = n * t - 1; i >= n * (t - 1); i--) {
      if (max < dp[i]) {
        max = dp[i];
      }
    }
    cout << max << endl;
  } else {
    int newarr[(n * n) + n];
    for (int j = 0; j < (n * n) + n; j++) {
      newarr[j] = a[j % n];
    }
    int dp[n * n + n];
    LIS(dp, newarr, (n * n) + n);
    int rem = t - (n + 1);
    int tempnew[n];
    for (int j = 0; j < n; j++) {
      tempnew[j] =
          dp[j + (n * n)] + rem * (dp[j + (n * n)] - dp[j + (n * n) - n]);
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
      if (max < tempnew[i]) {
        max = tempnew[i];
      }
    }
    cout << max << endl;
  }
  return 0;
}

```