#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
int abuse(vector<int> kt) {
  vector<int> tl(kt.size() + 1, INF);
  tl[0] = -INF;
  int res = 0;
  for (int i = 0; i < kt.size(); i++) {
    int ind = upper_bound(tl.begin(), tl.end(), kt[i]) - tl.begin();
    if (kt[i] < tl[ind] && kt[i] >= tl[ind - 1]) {
      tl[ind] = kt[i];
      res = max(ind, res);
    }
  }
  return res;
}
int main() {
  int n, t;
  cin >> n >> t;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t <= 605) {
    vector<int> coop(n * t);
    for (int i = 0; i < t; i++) {
      for (int j = 0; j < n; j++) {
        coop[i * n + j] = a[j];
      }
    }
    cout << abuse(coop) << endl;
  } else {
    map<int, int> m;
    int nicenum = -INF;
    for (int i = 0; i < n; i++) m[a[i]]++;
    for (auto p : m) {
      if (p.second > m[nicenum]) {
        nicenum = p.first;
      }
    }
    vector<int> beg, ed;
    for (int i = 0; i < n; i++) {
      if (a[i] <= nicenum) beg.push_back(a[i]);
      if (a[i] >= nicenum) ed.push_back(a[i]);
    }
    vector<int> beg_coop(300 * beg.size()), ed_coop(300 * ed.size());
    for (int i = 0; i < 300; i++) {
      for (int j = 0; j < (int)beg.size(); j++) {
        beg_coop[i * beg.size() + j] = beg[j];
      }
      for (int j = 0; j < (int)ed.size(); j++) {
        ed_coop[i * ed.size() + j] = ed[j];
      }
    }
    cout << abuse(beg_coop) + abuse(ed_coop) + (t - 600) * m[nicenum] << endl;
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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 = 2000000000;
int abuse(vector<int> kt) {
  vector<int> tl(kt.size() + 1, INF);
  tl[0] = -INF;
  int res = 0;
  for (int i = 0; i < kt.size(); i++) {
    int ind = upper_bound(tl.begin(), tl.end(), kt[i]) - tl.begin();
    if (kt[i] < tl[ind] && kt[i] >= tl[ind - 1]) {
      tl[ind] = kt[i];
      res = max(ind, res);
    }
  }
  return res;
}
int main() {
  int n, t;
  cin >> n >> t;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t <= 605) {
    vector<int> coop(n * t);
    for (int i = 0; i < t; i++) {
      for (int j = 0; j < n; j++) {
        coop[i * n + j] = a[j];
      }
    }
    cout << abuse(coop) << endl;
  } else {
    map<int, int> m;
    int nicenum = -INF;
    for (int i = 0; i < n; i++) m[a[i]]++;
    for (auto p : m) {
      if (p.second > m[nicenum]) {
        nicenum = p.first;
      }
    }
    vector<int> beg, ed;
    for (int i = 0; i < n; i++) {
      if (a[i] <= nicenum) beg.push_back(a[i]);
      if (a[i] >= nicenum) ed.push_back(a[i]);
    }
    vector<int> beg_coop(300 * beg.size()), ed_coop(300 * ed.size());
    for (int i = 0; i < 300; i++) {
      for (int j = 0; j < (int)beg.size(); j++) {
        beg_coop[i * beg.size() + j] = beg[j];
      }
      for (int j = 0; j < (int)ed.size(); j++) {
        ed_coop[i * ed.size() + j] = ed[j];
      }
    }
    cout << abuse(beg_coop) + abuse(ed_coop) + (t - 600) * m[nicenum] << endl;
  }
  return 0;
}

```