#include <bits/stdc++.h>
using namespace std;
int n, T;
int a[101], cnt[401];
vector<int> seq;
int dp[301][10001];
int cache[301][10001];
int solve(int maxi) {
  int ret = 0;
  for (int i = seq.size() - 1; i >= 0; i--) {
    if (seq[i] > maxi) continue;
    for (int j = i + 1; j < seq.size(); j++) {
      if (seq[j] >= seq[i]) dp[maxi][i] = max(dp[maxi][i], dp[maxi][j] + 1);
    }
    ret = max(ret, dp[maxi][i]);
  }
  return ret;
}
int binary(const vector<int>& in, int ind, int val, const int maxK) {
  if (in[ind - 1] <= val && val < in[ind]) return ind;
  if (val < in[ind])
    return binary(in, (ind + 1) / 2, val, ind);
  else
    return binary(in, (ind + maxK) / 2, val, maxK);
}
int lis(int maxi) {
  int len = seq.size();
  vector<int> c = vector<int>(len + 2, 303);
  int firstMin = -1;
  c[0] = -1;
  for (int i = 0; i < len; i++) {
    if (seq[i] <= maxi) {
      c[1] = seq[i];
      cache[maxi][i] = 1;
      firstMin = i;
      break;
    }
  }
  if (firstMin == -1) return 0;
  int sz = 1;
  for (int i = firstMin + 1; i < seq.size(); i++) {
    if (seq[i] > maxi) continue;
    if (seq[i] < c[1]) {
      c[1] = seq[i];
      cache[maxi][i] = 1;
    } else if (seq[i] >= c[sz]) {
      sz++;
      c[sz] = seq[i];
      cache[maxi][i] = sz;
    } else {
      int k = binary(c, sz, seq[i], sz);
      c[k] = seq[i];
      cache[maxi][i] = k;
    }
  }
  c.clear();
  return sz;
}
int lis2(int mini) {
  int len = seq.size();
  vector<int> c = vector<int>(len + 2, 303);
  int firstMin = -1;
  c[0] = -1;
  for (int i = 0; i < len; i++) {
    if (seq[i] >= mini) {
      c[1] = seq[i];
      firstMin = i;
      break;
    }
  }
  if (firstMin == -1) return 0;
  int sz = 1;
  for (int i = firstMin + 1; i < seq.size(); i++) {
    if (seq[i] < mini) continue;
    if (seq[i] < c[1]) {
      c[1] = seq[i];
    } else if (seq[i] >= c[sz]) {
      sz++;
      c[sz] = seq[i];
    } else {
      int k = binary(c, sz, seq[i], sz);
      c[k] = seq[i];
    }
  }
  c.clear();
  return sz;
}
int main() {
  cin >> n >> T;
  memset(a, 0, sizeof(a));
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < 301; i++)
    for (int j = 0; j < 10001; j++) cache[i][j] = 0;
  seq.clear();
  for (int i = 0; i < n; i++) cin >> a[i];
  int ret = 0;
  if (T <= 2 * n) {
    for (int i = 0; i < T; i++)
      for (int j = 0; j < n; j++) seq.push_back(a[j]);
    ret = lis(300);
    cout << ret << endl;
    return 0;
  } else {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) seq.push_back(a[j]);
    for (int j = 0; j < n; j++) cnt[a[j]]++;
    for (int i = 1; i < 301; i++) lis(i);
    for (int i = 1; i < 301; i++) {
      int pre = 0;
      pre = lis(i);
      int suf = 0;
      suf = lis2(i);
      ret = max(ret, cnt[i] * (T - (2 * n)) + pre + suf);
    }
    cout << ret << endl;
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
int n, T;
int a[101], cnt[401];
vector<int> seq;
int dp[301][10001];
int cache[301][10001];
int solve(int maxi) {
  int ret = 0;
  for (int i = seq.size() - 1; i >= 0; i--) {
    if (seq[i] > maxi) continue;
    for (int j = i + 1; j < seq.size(); j++) {
      if (seq[j] >= seq[i]) dp[maxi][i] = max(dp[maxi][i], dp[maxi][j] + 1);
    }
    ret = max(ret, dp[maxi][i]);
  }
  return ret;
}
int binary(const vector<int>& in, int ind, int val, const int maxK) {
  if (in[ind - 1] <= val && val < in[ind]) return ind;
  if (val < in[ind])
    return binary(in, (ind + 1) / 2, val, ind);
  else
    return binary(in, (ind + maxK) / 2, val, maxK);
}
int lis(int maxi) {
  int len = seq.size();
  vector<int> c = vector<int>(len + 2, 303);
  int firstMin = -1;
  c[0] = -1;
  for (int i = 0; i < len; i++) {
    if (seq[i] <= maxi) {
      c[1] = seq[i];
      cache[maxi][i] = 1;
      firstMin = i;
      break;
    }
  }
  if (firstMin == -1) return 0;
  int sz = 1;
  for (int i = firstMin + 1; i < seq.size(); i++) {
    if (seq[i] > maxi) continue;
    if (seq[i] < c[1]) {
      c[1] = seq[i];
      cache[maxi][i] = 1;
    } else if (seq[i] >= c[sz]) {
      sz++;
      c[sz] = seq[i];
      cache[maxi][i] = sz;
    } else {
      int k = binary(c, sz, seq[i], sz);
      c[k] = seq[i];
      cache[maxi][i] = k;
    }
  }
  c.clear();
  return sz;
}
int lis2(int mini) {
  int len = seq.size();
  vector<int> c = vector<int>(len + 2, 303);
  int firstMin = -1;
  c[0] = -1;
  for (int i = 0; i < len; i++) {
    if (seq[i] >= mini) {
      c[1] = seq[i];
      firstMin = i;
      break;
    }
  }
  if (firstMin == -1) return 0;
  int sz = 1;
  for (int i = firstMin + 1; i < seq.size(); i++) {
    if (seq[i] < mini) continue;
    if (seq[i] < c[1]) {
      c[1] = seq[i];
    } else if (seq[i] >= c[sz]) {
      sz++;
      c[sz] = seq[i];
    } else {
      int k = binary(c, sz, seq[i], sz);
      c[k] = seq[i];
    }
  }
  c.clear();
  return sz;
}
int main() {
  cin >> n >> T;
  memset(a, 0, sizeof(a));
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < 301; i++)
    for (int j = 0; j < 10001; j++) cache[i][j] = 0;
  seq.clear();
  for (int i = 0; i < n; i++) cin >> a[i];
  int ret = 0;
  if (T <= 2 * n) {
    for (int i = 0; i < T; i++)
      for (int j = 0; j < n; j++) seq.push_back(a[j]);
    ret = lis(300);
    cout << ret << endl;
    return 0;
  } else {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) seq.push_back(a[j]);
    for (int j = 0; j < n; j++) cnt[a[j]]++;
    for (int i = 1; i < 301; i++) lis(i);
    for (int i = 1; i < 301; i++) {
      int pre = 0;
      pre = lis(i);
      int suf = 0;
      suf = lis2(i);
      ret = max(ret, cnt[i] * (T - (2 * n)) + pre + suf);
    }
    cout << ret << endl;
  }
  return 0;
}

```