#include <bits/stdc++.h>
using namespace std;
int n, t, a[10000];
int t1, t2, r[10000], l1;
int q0, q2[10000];
int calc(int k) {
  if (k >= l1) return 0;
  if (r[k]) return r[k];
  int rk = 1, qk = 0, rp;
  for (int i = 0, p = k + 1; i < n && p < l1; ++i, ++p) {
    if (a[p] >= a[k] && (rp = 1 + calc(p)) > rk) {
      rk = rp;
      qk = p;
    }
  }
  r[k] = rk;
  q2[k] = qk;
  return rk;
}
int main(int argn, char* args[]) {
  cin >> n >> t;
  for (int i = 0; i < n; ++i) cin >> a[i];
  if (t <= 100) {
    t1 = t;
    t2 = 0;
  } else {
    t1 = 100;
    t2 = t - 100;
  }
  l1 = t1 * n;
  t2 = (t <= 100 ? 0 : t - 100);
  for (int p = n; p < l1; ++p) a[p] = a[p - n];
  int rm = 0, rk;
  for (int k = 0; k < n; ++k) {
    if ((rk = calc(k)) > rm) {
      rm = rk;
      q0 = k;
    }
  }
  if (t2 > 0) {
    int qb = -1, qc = 0;
    for (int q = q2[q0]; q > 0 && q < l1; q = q2[q]) {
      if (a[q] == a[qb]) {
        qc += 1;
        if (q == qb + n) {
          rm += qc * t2;
          break;
        }
      } else {
        qb = q;
        qc = 0;
      }
    }
  }
  cout << rm << endl;
  return 0;
}

### Prompt

Please formulate a cpp solution to 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 n, t, a[10000];
int t1, t2, r[10000], l1;
int q0, q2[10000];
int calc(int k) {
  if (k >= l1) return 0;
  if (r[k]) return r[k];
  int rk = 1, qk = 0, rp;
  for (int i = 0, p = k + 1; i < n && p < l1; ++i, ++p) {
    if (a[p] >= a[k] && (rp = 1 + calc(p)) > rk) {
      rk = rp;
      qk = p;
    }
  }
  r[k] = rk;
  q2[k] = qk;
  return rk;
}
int main(int argn, char* args[]) {
  cin >> n >> t;
  for (int i = 0; i < n; ++i) cin >> a[i];
  if (t <= 100) {
    t1 = t;
    t2 = 0;
  } else {
    t1 = 100;
    t2 = t - 100;
  }
  l1 = t1 * n;
  t2 = (t <= 100 ? 0 : t - 100);
  for (int p = n; p < l1; ++p) a[p] = a[p - n];
  int rm = 0, rk;
  for (int k = 0; k < n; ++k) {
    if ((rk = calc(k)) > rm) {
      rm = rk;
      q0 = k;
    }
  }
  if (t2 > 0) {
    int qb = -1, qc = 0;
    for (int q = q2[q0]; q > 0 && q < l1; q = q2[q]) {
      if (a[q] == a[qb]) {
        qc += 1;
        if (q == qb + n) {
          rm += qc * t2;
          break;
        }
      } else {
        qb = q;
        qc = 0;
      }
    }
  }
  cout << rm << endl;
  return 0;
}

```