#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, a[N], s[N], dp[N], f[N], mx[N];
vector<int> vec;
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    s[a[i]]++;
  }
  int t = min(m, 2000);
  for (int i = 1; i < t; i++) {
    for (int j = 0; j < n; j++) {
      a[i * n + j] = a[j];
    }
  }
  int sz = t * n, res = 0;
  for (int i = 0; i < sz; i++) {
    if (vec.size() == 0) {
      vec.push_back(a[i]);
      dp[i] = 1;
    } else {
      int t = upper_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
      if (t == vec.size())
        vec.push_back(a[i]);
      else
        vec[t] = a[i];
      dp[i] = t + 1;
    }
    res = max(res, dp[i]);
  }
  if (m == t) {
    cout << res << endl;
  } else {
    sz = n * 1000;
    vec.clear();
    for (int i = sz - 1; i >= 0; i--) {
      if (vec.size() == 0) {
        vec.push_back(-a[i]);
        f[i] = 1;
      } else {
        int t = upper_bound(vec.begin(), vec.end(), -a[i]) - vec.begin();
        if (t == vec.size())
          vec.push_back(-a[i]);
        else
          vec[t] = -a[i];
        f[i] = t + 1;
      }
    }
    for (int i = 0; i < sz; i++) {
      mx[a[i]] = max(mx[a[i]], dp[i] + (m - 2000) * s[a[i]]);
    }
    res = 0;
    for (int i = 0; i < sz; i++) {
      res = max(res, mx[a[i]] + f[i]);
    }
    cout << res << endl;
  }
}

### 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;
const int N = 200005;
int n, m, a[N], s[N], dp[N], f[N], mx[N];
vector<int> vec;
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    s[a[i]]++;
  }
  int t = min(m, 2000);
  for (int i = 1; i < t; i++) {
    for (int j = 0; j < n; j++) {
      a[i * n + j] = a[j];
    }
  }
  int sz = t * n, res = 0;
  for (int i = 0; i < sz; i++) {
    if (vec.size() == 0) {
      vec.push_back(a[i]);
      dp[i] = 1;
    } else {
      int t = upper_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
      if (t == vec.size())
        vec.push_back(a[i]);
      else
        vec[t] = a[i];
      dp[i] = t + 1;
    }
    res = max(res, dp[i]);
  }
  if (m == t) {
    cout << res << endl;
  } else {
    sz = n * 1000;
    vec.clear();
    for (int i = sz - 1; i >= 0; i--) {
      if (vec.size() == 0) {
        vec.push_back(-a[i]);
        f[i] = 1;
      } else {
        int t = upper_bound(vec.begin(), vec.end(), -a[i]) - vec.begin();
        if (t == vec.size())
          vec.push_back(-a[i]);
        else
          vec[t] = -a[i];
        f[i] = t + 1;
      }
    }
    for (int i = 0; i < sz; i++) {
      mx[a[i]] = max(mx[a[i]], dp[i] + (m - 2000) * s[a[i]]);
    }
    res = 0;
    for (int i = 0; i < sz; i++) {
      res = max(res, mx[a[i]] + f[i]);
    }
    cout << res << endl;
  }
}

```