#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int siz = 102;
long long inf = 1e15;
struct matrix {
  int row, col;
  long long data[siz][siz];
  matrix() {
    row = siz;
    col = siz;
    memset(data, 0, sizeof data);
  }
  void print() {
    printf("\n");
    for (int i = 0; i < row; ++i) {
      for (int j = 0; j < col; ++j) {
        printf("%lld ", data[i][j]);
      }
      printf("\n");
    }
    printf("\n");
  }
  matrix operator*(const matrix other) const {
    matrix result = matrix();
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < other.col; j++) {
        result.data[i][j] = -inf;
        for (int k = 0; k < col; k++) {
          result.data[i][j] =
              max(result.data[i][j], data[i][k] + other.data[k][j]);
        }
      }
    }
    result.row = row;
    result.col = col;
    return result;
  }
  void init() {
    memset(data, 0, sizeof(data));
    for (int i = 0; i < siz; ++i) data[i][i] = 0ll;
  }
  matrix pow_(long long n) {
    matrix ret;
    ret.init();
    if (n == 0) return ret;
    if (n == 1) return *this;
    matrix P = *this;
    while (n) {
      if (n & 1) {
        ret = ret * P;
      }
      n = n / 2ll;
      P = P * P;
    }
    return ret;
  }
};
long long mem[102][102], n, t, a[102];
int main() {
  scanf("%lld", &n);
  scanf("%lld", &t);
  for (int i = 0; i < n + 0; i++) {
    scanf("%lld", &a[i]);
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[j] < a[i]) {
        mem[i][j] = -inf;
        continue;
      }
      mem[i][j] = 1;
      for (int k = 0; k < j; k++)
        if (a[k] <= a[j]) {
          mem[i][j] = max(mem[i][j], mem[i][k] + 1ll);
        }
    }
  }
  matrix tr;
  tr.col = n;
  tr.row = n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      tr.data[i][j] = mem[i][j];
    }
  }
  tr = tr.pow_(t);
  long long ans = -inf;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans = max(ans, tr.data[i][j]);
    }
  }
  printf("%lld\n", ans);
}

### Prompt

Please create a solution in cpp 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>
#pragma GCC optimize("O3")
using namespace std;
const int siz = 102;
long long inf = 1e15;
struct matrix {
  int row, col;
  long long data[siz][siz];
  matrix() {
    row = siz;
    col = siz;
    memset(data, 0, sizeof data);
  }
  void print() {
    printf("\n");
    for (int i = 0; i < row; ++i) {
      for (int j = 0; j < col; ++j) {
        printf("%lld ", data[i][j]);
      }
      printf("\n");
    }
    printf("\n");
  }
  matrix operator*(const matrix other) const {
    matrix result = matrix();
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < other.col; j++) {
        result.data[i][j] = -inf;
        for (int k = 0; k < col; k++) {
          result.data[i][j] =
              max(result.data[i][j], data[i][k] + other.data[k][j]);
        }
      }
    }
    result.row = row;
    result.col = col;
    return result;
  }
  void init() {
    memset(data, 0, sizeof(data));
    for (int i = 0; i < siz; ++i) data[i][i] = 0ll;
  }
  matrix pow_(long long n) {
    matrix ret;
    ret.init();
    if (n == 0) return ret;
    if (n == 1) return *this;
    matrix P = *this;
    while (n) {
      if (n & 1) {
        ret = ret * P;
      }
      n = n / 2ll;
      P = P * P;
    }
    return ret;
  }
};
long long mem[102][102], n, t, a[102];
int main() {
  scanf("%lld", &n);
  scanf("%lld", &t);
  for (int i = 0; i < n + 0; i++) {
    scanf("%lld", &a[i]);
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[j] < a[i]) {
        mem[i][j] = -inf;
        continue;
      }
      mem[i][j] = 1;
      for (int k = 0; k < j; k++)
        if (a[k] <= a[j]) {
          mem[i][j] = max(mem[i][j], mem[i][k] + 1ll);
        }
    }
  }
  matrix tr;
  tr.col = n;
  tr.row = n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      tr.data[i][j] = mem[i][j];
    }
  }
  tr = tr.pow_(t);
  long long ans = -inf;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans = max(ans, tr.data[i][j]);
    }
  }
  printf("%lld\n", ans);
}

```