#include <bits/stdc++.h>
using namespace std;
int n, t, **m, **ans, a[100], init[100], seg[1 << 10], MOD = 1000000007;
int** make() {
  int** ans = new int*[n];
  for (int i = 0; i < n; i++) {
    ans[i] = new int[n];
    for (int j = 0; j < n; j++) ans[i][j] = 0;
  }
  return ans;
}
int** mult(int** x, int** y) {
  int** z = make();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) {
        if (a[i] > a[j])
          z[i][j] = -MOD;
        else
          z[i][j] = max(z[i][j], x[i][k] + y[k][j]);
      }
  return z;
}
void modify(int p, int value) {
  for (seg[p += 512] = value; p > 1; p >>= 1)
    seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) {
  int res = 0;
  for (l += 512, r += 512; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = max(res, seg[l++]);
    if (r & 1) res = max(res, seg[--r]);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> t;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    init[i] = query(1, a[i] + 1) + 1;
    modify(a[i], init[i]);
  }
  m = make(), ans = make();
  for (int i = 0; i < n; i++) {
    memset(seg, 0, sizeof seg);
    for (int j = i + 1; j < 2 * n; j++) {
      if (a[j % n] >= a[i]) {
        int x = query(a[i], a[j % n] + 1) + 1;
        modify(a[j % n], x);
        if (j >= n) m[i][j % n] = x;
      } else if (j >= n)
        m[i][j % n] = -MOD;
    }
  }
  t--;
  bool first = 0;
  if (t == 0) {
    int z = 0;
    for (int i = 0; i < n; i++) z = max(z, init[i]);
    cout << z;
    return 0;
  }
  while (t) {
    if (t % 2) {
      if (first == 0)
        first = 1, ans = m;
      else
        ans = mult(ans, m);
    }
    m = mult(m, m);
    t /= 2;
  }
  int z = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) z = max(ans[i][j] + init[i], z);
  cout << z;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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, **m, **ans, a[100], init[100], seg[1 << 10], MOD = 1000000007;
int** make() {
  int** ans = new int*[n];
  for (int i = 0; i < n; i++) {
    ans[i] = new int[n];
    for (int j = 0; j < n; j++) ans[i][j] = 0;
  }
  return ans;
}
int** mult(int** x, int** y) {
  int** z = make();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) {
        if (a[i] > a[j])
          z[i][j] = -MOD;
        else
          z[i][j] = max(z[i][j], x[i][k] + y[k][j]);
      }
  return z;
}
void modify(int p, int value) {
  for (seg[p += 512] = value; p > 1; p >>= 1)
    seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) {
  int res = 0;
  for (l += 512, r += 512; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = max(res, seg[l++]);
    if (r & 1) res = max(res, seg[--r]);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> t;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    init[i] = query(1, a[i] + 1) + 1;
    modify(a[i], init[i]);
  }
  m = make(), ans = make();
  for (int i = 0; i < n; i++) {
    memset(seg, 0, sizeof seg);
    for (int j = i + 1; j < 2 * n; j++) {
      if (a[j % n] >= a[i]) {
        int x = query(a[i], a[j % n] + 1) + 1;
        modify(a[j % n], x);
        if (j >= n) m[i][j % n] = x;
      } else if (j >= n)
        m[i][j % n] = -MOD;
    }
  }
  t--;
  bool first = 0;
  if (t == 0) {
    int z = 0;
    for (int i = 0; i < n; i++) z = max(z, init[i]);
    cout << z;
    return 0;
  }
  while (t) {
    if (t % 2) {
      if (first == 0)
        first = 1, ans = m;
      else
        ans = mult(ans, m);
    }
    m = mult(m, m);
    t /= 2;
  }
  int z = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) z = max(ans[i][j] + init[i], z);
  cout << z;
}

```