#include <bits/stdc++.h>
using namespace std;
int solve_slow(vector<int> a, int t) {
  int n = (int)a.size();
  vector<int> dp(n * t, 0);
  for (int i = 0; i < n * t; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j % n] <= a[i % n]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
  }
  return *max_element(dp.begin(), dp.end());
}
int solve_fast(vector<int> a, int t) {
  int n = (int)a.size();
  vector<int> seen;
  {
    for (auto t : a) {
      seen.push_back(t);
    }
    sort(seen.begin(), seen.end());
    seen.resize(unique(seen.begin(), seen.end()) - seen.begin());
    for (auto &t : a) {
      int ind = lower_bound(seen.begin(), seen.end(), t) - seen.begin();
      t = ind;
    }
  }
  vector<vector<int>> base(n, vector<int>(n));
  auto calc = [&](int l, int r) {
    vector<int> to;
    for (auto t : a) {
      if (l <= t && t <= r) {
        to.push_back(t);
      }
    }
    if (to.empty()) {
      return 0;
    }
    vector<int> dp(to.size(), 1);
    for (int i = 1; i < (int)to.size(); i++) {
      for (int j = 0; j < i; j++) {
        if (to[j] <= to[i]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
    return *max_element(dp.begin(), dp.end());
  };
  int ssz = (int)seen.size();
  vector<vector<int>> b(ssz, vector<int>(ssz));
  for (int i = 0; i < ssz; i++) {
    for (int j = 0; j < ssz; j++) {
      b[i][j] = calc(i, j);
    }
  }
  vector<vector<int>> cur(ssz, vector<int>(ssz));
  auto mul = [&](vector<vector<int>> &f, vector<vector<int>> &s) {
    vector<vector<int>> res(ssz, vector<int>(ssz));
    for (int i = 0; i < ssz; i++) {
      for (int j = 0; j < ssz; j++) {
        for (int k = i; k <= j; k++) {
          res[i][j] = max(res[i][j], f[i][k] + s[k][j]);
        }
      }
    }
    return res;
  };
  while (t > 0) {
    if (t & 1) {
      cur = mul(cur, b);
    }
    b = mul(b, b);
    t >>= 1;
  }
  int ans = 0;
  for (int i = 0; i < ssz; i++) {
    for (int j = 0; j < ssz; j++) {
      ans = max(ans, cur[i][j]);
    }
  }
  return ans;
}
void stress() {
  srand(time(0));
  int n = 10;
  int t = 12;
  int MAX_NUM = 10;
  while (true) {
    vector<int> a(n);
    for (auto &t : a) {
      t = rand() % MAX_NUM;
    }
    cerr << "TEST" << endl;
    cerr << n << ' ' << t << endl;
    for (auto t : a) {
      cerr << t << ' ';
    }
    cerr << endl;
    int f = solve_slow(a, t);
    int s = solve_fast(a, t);
    if (f != s) {
      cerr << "WA" << endl;
      exit(0);
    } else {
      cerr << "OK" << endl;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  bool STRESS = false;
  if (STRESS) {
    stress();
  } else {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (auto &t : a) {
      cin >> t;
    }
    cout << solve_fast(a, t) << endl;
  }
}

### 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;
int solve_slow(vector<int> a, int t) {
  int n = (int)a.size();
  vector<int> dp(n * t, 0);
  for (int i = 0; i < n * t; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j % n] <= a[i % n]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
  }
  return *max_element(dp.begin(), dp.end());
}
int solve_fast(vector<int> a, int t) {
  int n = (int)a.size();
  vector<int> seen;
  {
    for (auto t : a) {
      seen.push_back(t);
    }
    sort(seen.begin(), seen.end());
    seen.resize(unique(seen.begin(), seen.end()) - seen.begin());
    for (auto &t : a) {
      int ind = lower_bound(seen.begin(), seen.end(), t) - seen.begin();
      t = ind;
    }
  }
  vector<vector<int>> base(n, vector<int>(n));
  auto calc = [&](int l, int r) {
    vector<int> to;
    for (auto t : a) {
      if (l <= t && t <= r) {
        to.push_back(t);
      }
    }
    if (to.empty()) {
      return 0;
    }
    vector<int> dp(to.size(), 1);
    for (int i = 1; i < (int)to.size(); i++) {
      for (int j = 0; j < i; j++) {
        if (to[j] <= to[i]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
    return *max_element(dp.begin(), dp.end());
  };
  int ssz = (int)seen.size();
  vector<vector<int>> b(ssz, vector<int>(ssz));
  for (int i = 0; i < ssz; i++) {
    for (int j = 0; j < ssz; j++) {
      b[i][j] = calc(i, j);
    }
  }
  vector<vector<int>> cur(ssz, vector<int>(ssz));
  auto mul = [&](vector<vector<int>> &f, vector<vector<int>> &s) {
    vector<vector<int>> res(ssz, vector<int>(ssz));
    for (int i = 0; i < ssz; i++) {
      for (int j = 0; j < ssz; j++) {
        for (int k = i; k <= j; k++) {
          res[i][j] = max(res[i][j], f[i][k] + s[k][j]);
        }
      }
    }
    return res;
  };
  while (t > 0) {
    if (t & 1) {
      cur = mul(cur, b);
    }
    b = mul(b, b);
    t >>= 1;
  }
  int ans = 0;
  for (int i = 0; i < ssz; i++) {
    for (int j = 0; j < ssz; j++) {
      ans = max(ans, cur[i][j]);
    }
  }
  return ans;
}
void stress() {
  srand(time(0));
  int n = 10;
  int t = 12;
  int MAX_NUM = 10;
  while (true) {
    vector<int> a(n);
    for (auto &t : a) {
      t = rand() % MAX_NUM;
    }
    cerr << "TEST" << endl;
    cerr << n << ' ' << t << endl;
    for (auto t : a) {
      cerr << t << ' ';
    }
    cerr << endl;
    int f = solve_slow(a, t);
    int s = solve_fast(a, t);
    if (f != s) {
      cerr << "WA" << endl;
      exit(0);
    } else {
      cerr << "OK" << endl;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  bool STRESS = false;
  if (STRESS) {
    stress();
  } else {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (auto &t : a) {
      cin >> t;
    }
    cout << solve_fast(a, t) << endl;
  }
}

```