#include <bits/stdc++.h>
int arr[4000000];
using namespace std;
vector<int> v;
int lis(int n) {
  v.clear();
  v.push_back(arr[0]);
  for (int i = 1; i < n; ++i) {
    if (arr[i] >= v.back())
      v.push_back(arr[i]);
    else
      *upper_bound(v.begin(), v.end(), arr[i]) = arr[i];
  }
  return v.size();
}
int main(void) {
  int n, t;
  cin >> n >> t;
  for (int i = 0; i < n; ++i) cin >> arr[i];
  if (t < 10000) {
    for (int i = n; i < n * t; ++i) arr[i] = arr[i - n];
    int ans = lis(n * t);
    cout << ans;
  } else {
    for (int i = n; i < n * 10000; ++i) arr[i] = arr[i - n];
    int ans = lis(n * 10000);
    int mx = 0;
    int temp[301] = {0};
    for (int i = 0; i < n; ++i) temp[arr[i]]++;
    for (int i = 0; i < 301; ++i) mx = max(temp[i], mx);
    ans += mx * (t - 10000);
    cout << ans;
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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>
int arr[4000000];
using namespace std;
vector<int> v;
int lis(int n) {
  v.clear();
  v.push_back(arr[0]);
  for (int i = 1; i < n; ++i) {
    if (arr[i] >= v.back())
      v.push_back(arr[i]);
    else
      *upper_bound(v.begin(), v.end(), arr[i]) = arr[i];
  }
  return v.size();
}
int main(void) {
  int n, t;
  cin >> n >> t;
  for (int i = 0; i < n; ++i) cin >> arr[i];
  if (t < 10000) {
    for (int i = n; i < n * t; ++i) arr[i] = arr[i - n];
    int ans = lis(n * t);
    cout << ans;
  } else {
    for (int i = n; i < n * 10000; ++i) arr[i] = arr[i - n];
    int ans = lis(n * 10000);
    int mx = 0;
    int temp[301] = {0};
    for (int i = 0; i < n; ++i) temp[arr[i]]++;
    for (int i = 0; i < 301; ++i) mx = max(temp[i], mx);
    ans += mx * (t - 10000);
    cout << ans;
  }
  return 0;
}

```