#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max();
inline int pow2(int k) { return 1 << k; }
class RMQ {
  int K, N;
  vector<int> t;

 public:
  RMQ(const vector<int> &a);
  int get(int l, int r);
  void set(int pos, int val);
  void print();
};
RMQ::RMQ(const vector<int> &a) {
  N = a.size();
  if (N < 1) {
    return;
  }
  K = 0;
  while (N > pow2(K)) {
    K++;
  }
  K++;
  t.resize(pow2(K));
  for (int i = 0; i < N; i++) {
    t[pow2(K - 1) + i] = a[i];
  }
  int len = N;
  for (int k = K - 1; k > 0; k--) {
    int i;
    for (i = pow2(k - 1); i < pow2(k - 1) + len / 2; i++) {
      t[i] = max(t[2 * i], t[2 * i + 1]);
    }
    if (len % 2 == 1) {
      t[i] = t[2 * i];
    }
    len = len / 2 + len % 2;
  }
}
int RMQ::get(int l, int r) {
  l += pow2(K - 1);
  r += pow2(K - 1);
  int maxl = t[l];
  int maxr = t[r];
  while (r - l > 1) {
    int l1 = l / 2;
    if (l % 2 == 0) {
      maxl = max(t[l + 1], maxl);
    }
    l = l1;
    int r1 = r / 2;
    if (r % 2 == 1) {
      maxr = max(t[r - 1], maxr);
    }
    r = r1;
  }
  return max(maxl, maxr);
}
void RMQ::set(int pos, int val) {
  pos = pow2(K - 1) + pos;
  t[pos] = val;
  while (pos > 0) {
    pos = pos / 2;
    t[pos] = max(t[2 * pos], t[2 * pos + 1]);
  }
}
void RMQ::print() {
  cout << K << ' ' << N << endl;
  cout << endl;
  for (int k = K - 1; k >= 0; k--) {
    for (int i = pow2(k); i < pow2(k + 1); i++) {
      cout << t[i] << ' ';
    }
    cout << endl;
  }
}
int rmqtest() {
  vector<int> a;
  int alist[] = {7, 7, 7, 7, 3, 2};
  for (size_t i = 0; i < sizeof(alist) / sizeof(int); i++) {
    a.push_back(alist[i]);
  }
  RMQ r = RMQ(a);
  cout << "rmq test1" << endl;
  r.print();
  cout << "rmq test2" << endl;
  r.set(2, 8);
  r.print();
  cout << "rmq test3" << endl;
  cout << r.get(1, 4);
  return 0;
}
int n, t;
const int A = 300;
vector<long> a;
int solve(int L) {
  vector<int> v(A + 1, 0);
  v[a[0]] = 1;
  RMQ rmq(v);
  for (int i = 1; i < L; i++) {
    long ai = a[i % n];
    int max = rmq.get(1, ai);
    rmq.set(ai, max + 1);
  }
  return rmq.get(1, A);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> t;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t > n) {
    int r1 = solve(n * n);
    int r2 = solve(n * (n + 1));
    cout << r1 + (r2 - r1) * (t - n) << '\n';
  } else
    cout << solve(n * t) << '\n';
  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;
const int INF = numeric_limits<int>::max();
inline int pow2(int k) { return 1 << k; }
class RMQ {
  int K, N;
  vector<int> t;

 public:
  RMQ(const vector<int> &a);
  int get(int l, int r);
  void set(int pos, int val);
  void print();
};
RMQ::RMQ(const vector<int> &a) {
  N = a.size();
  if (N < 1) {
    return;
  }
  K = 0;
  while (N > pow2(K)) {
    K++;
  }
  K++;
  t.resize(pow2(K));
  for (int i = 0; i < N; i++) {
    t[pow2(K - 1) + i] = a[i];
  }
  int len = N;
  for (int k = K - 1; k > 0; k--) {
    int i;
    for (i = pow2(k - 1); i < pow2(k - 1) + len / 2; i++) {
      t[i] = max(t[2 * i], t[2 * i + 1]);
    }
    if (len % 2 == 1) {
      t[i] = t[2 * i];
    }
    len = len / 2 + len % 2;
  }
}
int RMQ::get(int l, int r) {
  l += pow2(K - 1);
  r += pow2(K - 1);
  int maxl = t[l];
  int maxr = t[r];
  while (r - l > 1) {
    int l1 = l / 2;
    if (l % 2 == 0) {
      maxl = max(t[l + 1], maxl);
    }
    l = l1;
    int r1 = r / 2;
    if (r % 2 == 1) {
      maxr = max(t[r - 1], maxr);
    }
    r = r1;
  }
  return max(maxl, maxr);
}
void RMQ::set(int pos, int val) {
  pos = pow2(K - 1) + pos;
  t[pos] = val;
  while (pos > 0) {
    pos = pos / 2;
    t[pos] = max(t[2 * pos], t[2 * pos + 1]);
  }
}
void RMQ::print() {
  cout << K << ' ' << N << endl;
  cout << endl;
  for (int k = K - 1; k >= 0; k--) {
    for (int i = pow2(k); i < pow2(k + 1); i++) {
      cout << t[i] << ' ';
    }
    cout << endl;
  }
}
int rmqtest() {
  vector<int> a;
  int alist[] = {7, 7, 7, 7, 3, 2};
  for (size_t i = 0; i < sizeof(alist) / sizeof(int); i++) {
    a.push_back(alist[i]);
  }
  RMQ r = RMQ(a);
  cout << "rmq test1" << endl;
  r.print();
  cout << "rmq test2" << endl;
  r.set(2, 8);
  r.print();
  cout << "rmq test3" << endl;
  cout << r.get(1, 4);
  return 0;
}
int n, t;
const int A = 300;
vector<long> a;
int solve(int L) {
  vector<int> v(A + 1, 0);
  v[a[0]] = 1;
  RMQ rmq(v);
  for (int i = 1; i < L; i++) {
    long ai = a[i % n];
    int max = rmq.get(1, ai);
    rmq.set(ai, max + 1);
  }
  return rmq.get(1, A);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> t;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (t > n) {
    int r1 = solve(n * n);
    int r2 = solve(n * (n + 1));
    cout << r1 + (r2 - r1) * (t - n) << '\n';
  } else
    cout << solve(n * t) << '\n';
  return 0;
}

```