#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
vector<int> data;
struct Matrix {
  int mat[301][301];
  Matrix(int init = -1000000000) {
    for (int i = 0; i < 301; i++)
      for (int j = 0; j < 301; j++) mat[i][j] = init;
  }
  Matrix operator*(const Matrix &b) const {
    Matrix c;
    for (int i = 1; i < 301; i++)
      for (int j = i; j < 301; j++)
        for (int k = i; k <= j; k++)
          c.mat[i][j] = max(c.mat[i][j], mat[i][k] + b.mat[k][j]);
    return c;
  }
  Matrix power(long long pw) {
    auto cur = *this;
    Matrix R(0);
    while (pw) {
      if (pw & 1ll) R = R * cur;
      pw >>= 1;
      cur = cur * cur;
    }
    return R;
  }
};
int n, T;
int LNDS(int lo, int hi) {
  multiset<int> l;
  for (int i = 0; i < n; i++) {
    int x = data[i];
    if (x < lo || hi < x) continue;
    auto it = l.upper_bound(x);
    if (it == l.end()) {
      l.insert(x);
    } else {
      l.erase(it);
      l.insert(x);
    }
  }
  return int((l).size()) == 0 ? -1000000000 : int((l).size());
}
int main() {
  fastIO();
  cin >> n >> T;
  data.resize(n);
  for (int i = 0; i < n; i++) cin >> data[i];
  Matrix res;
  for (int i = 1; i < 301; i++)
    for (int j = i; j < 301; j++) res.mat[i][j] = LNDS(i, j);
  cout << res.power(T).mat[1][300] << endl;
  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>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
vector<int> data;
struct Matrix {
  int mat[301][301];
  Matrix(int init = -1000000000) {
    for (int i = 0; i < 301; i++)
      for (int j = 0; j < 301; j++) mat[i][j] = init;
  }
  Matrix operator*(const Matrix &b) const {
    Matrix c;
    for (int i = 1; i < 301; i++)
      for (int j = i; j < 301; j++)
        for (int k = i; k <= j; k++)
          c.mat[i][j] = max(c.mat[i][j], mat[i][k] + b.mat[k][j]);
    return c;
  }
  Matrix power(long long pw) {
    auto cur = *this;
    Matrix R(0);
    while (pw) {
      if (pw & 1ll) R = R * cur;
      pw >>= 1;
      cur = cur * cur;
    }
    return R;
  }
};
int n, T;
int LNDS(int lo, int hi) {
  multiset<int> l;
  for (int i = 0; i < n; i++) {
    int x = data[i];
    if (x < lo || hi < x) continue;
    auto it = l.upper_bound(x);
    if (it == l.end()) {
      l.insert(x);
    } else {
      l.erase(it);
      l.insert(x);
    }
  }
  return int((l).size()) == 0 ? -1000000000 : int((l).size());
}
int main() {
  fastIO();
  cin >> n >> T;
  data.resize(n);
  for (int i = 0; i < n; i++) cin >> data[i];
  Matrix res;
  for (int i = 1; i < 301; i++)
    for (int j = i; j < 301; j++) res.mat[i][j] = LNDS(i, j);
  cout << res.power(T).mat[1][300] << endl;
  return 0;
}

```