#include <bits/stdc++.h>
using namespace std;
void completar(vector<int> &v, int T) {
  int n = v.size();
  for (int i = 1; i < T; i++)
    for (int k = 0; k < n; k++) v.push_back(v[k]);
}
vector<int> fA(vector<int> &v) {
  vector<int> dp(v.size() + 1, (1 << 30)), ans(v.size());
  dp[0] = -(1 << 30);
  for (int i = 0; i < v.size(); i++) {
    ans[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
    dp[ans[i]] = v[i];
  }
  return ans;
}
vector<int> fB(vector<int> &v) {
  int maximo = *max_element(v.begin(), v.end()) + 1;
  vector<int> dp(v.size() + 1, (1 << 30)), ans(v.size());
  dp[0] = -(1 << 30);
  for (int i = v.size() - 1; i >= 0; i--) {
    ans[i] = upper_bound(dp.begin(), dp.end(), maximo - v[i]) - dp.begin();
    dp[ans[i]] = maximo - v[i];
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, T;
  cin >> n >> T;
  vector<int> v(n), fin, ini;
  for (int i = 0; i < n; i++) cin >> v[i];
  if (T <= 2 * n) {
    completar(v, T);
    fin = fA(v);
    cout << *max_element(fin.begin(), fin.end()) << endl;
  } else {
    int ans = 0;
    completar(v, n);
    fin = fA(v);
    ini = fB(v);
    for (int i = 0; i < n; i++) {
      int cnt = 0;
      for (int k = 0; k < n; k++)
        if (v[i] == v[k]) cnt++;
      for (int k = 0; k < n; k++) {
        if (v[i] <= v[k])
          ans = max(ans, fin[(n - 1) * n + i] + (T - 2 * n) * cnt + ini[k]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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;
void completar(vector<int> &v, int T) {
  int n = v.size();
  for (int i = 1; i < T; i++)
    for (int k = 0; k < n; k++) v.push_back(v[k]);
}
vector<int> fA(vector<int> &v) {
  vector<int> dp(v.size() + 1, (1 << 30)), ans(v.size());
  dp[0] = -(1 << 30);
  for (int i = 0; i < v.size(); i++) {
    ans[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
    dp[ans[i]] = v[i];
  }
  return ans;
}
vector<int> fB(vector<int> &v) {
  int maximo = *max_element(v.begin(), v.end()) + 1;
  vector<int> dp(v.size() + 1, (1 << 30)), ans(v.size());
  dp[0] = -(1 << 30);
  for (int i = v.size() - 1; i >= 0; i--) {
    ans[i] = upper_bound(dp.begin(), dp.end(), maximo - v[i]) - dp.begin();
    dp[ans[i]] = maximo - v[i];
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, T;
  cin >> n >> T;
  vector<int> v(n), fin, ini;
  for (int i = 0; i < n; i++) cin >> v[i];
  if (T <= 2 * n) {
    completar(v, T);
    fin = fA(v);
    cout << *max_element(fin.begin(), fin.end()) << endl;
  } else {
    int ans = 0;
    completar(v, n);
    fin = fA(v);
    ini = fB(v);
    for (int i = 0; i < n; i++) {
      int cnt = 0;
      for (int k = 0; k < n; k++)
        if (v[i] == v[k]) cnt++;
      for (int k = 0; k < n; k++) {
        if (v[i] <= v[k])
          ans = max(ans, fin[(n - 1) * n + i] + (T - 2 * n) * cnt + ini[k]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}

```