#include <bits/stdc++.h>
using namespace std;
const int N = 300 + 5;
int a[N], x[N][N], dp[N][N];
void checkmax(int &x, int val) {
  if (x < val) x = val;
}
int m;
void calc_dp() {
  for (int st = 0; st < m; st++) {
    for (int ed = m - 1; ed >= st; ed--) {
      for (int k = ed; k >= st; k--) {
        checkmax(dp[st][ed], dp[st][k] + x[k][ed]);
      }
    }
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(dp[st][ed], dp[st][ed - 1]);
    }
  }
}
void calc_x() {
  static int temp[N][N];
  for (int st = 0; st < m; st++)
    for (int ed = 0; ed < m; ed++) temp[st][ed] = -1;
  for (int st = 0; st < m; st++) {
    for (int ed = m - 1; ed >= st; ed--) {
      for (int k = ed; k >= st; k--) {
        checkmax(temp[st][ed], x[st][k] + x[k][ed]);
      }
    }
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(temp[st][ed], temp[st][ed - 1]);
    }
    for (int ed = 0; ed < m; ed++) {
      x[st][ed] = temp[st][ed];
    }
  }
}
void Bin(int K) {
  while (K) {
    if (K & 1) {
      calc_dp();
    }
    calc_x();
    K >>= 1;
  }
}
int b[N];
int main() {
  int n, T;
  scanf("%d%d", &n, &T);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b, b + n);
  m = unique(b, b + n) - b;
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(b, b + m, a[i]) - b;
  }
  memset(x, -1, sizeof x);
  x[a[0]][a[0]] = 1;
  for (int i = 1; i < n; i++) {
    for (int st = 0; st < a[i] + 1; st++) {
      for (int ed = a[i]; ed >= st; ed--) {
        if (~x[st][ed]) {
          checkmax(x[st][a[i]], x[st][ed] + 1);
        }
      }
    }
    checkmax(x[a[i]][a[i]], 1);
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(x[st][ed], x[st][ed - 1]);
    }
  }
  Bin(T);
  int answer = 0;
  for (int st = 0; st < m; st++)
    for (int ed = 0; ed < m; ed++) checkmax(answer, dp[st][ed]);
  printf("%d\n", answer);
  return 0;
}

### Prompt

Develop a solution in Cpp 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;
const int N = 300 + 5;
int a[N], x[N][N], dp[N][N];
void checkmax(int &x, int val) {
  if (x < val) x = val;
}
int m;
void calc_dp() {
  for (int st = 0; st < m; st++) {
    for (int ed = m - 1; ed >= st; ed--) {
      for (int k = ed; k >= st; k--) {
        checkmax(dp[st][ed], dp[st][k] + x[k][ed]);
      }
    }
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(dp[st][ed], dp[st][ed - 1]);
    }
  }
}
void calc_x() {
  static int temp[N][N];
  for (int st = 0; st < m; st++)
    for (int ed = 0; ed < m; ed++) temp[st][ed] = -1;
  for (int st = 0; st < m; st++) {
    for (int ed = m - 1; ed >= st; ed--) {
      for (int k = ed; k >= st; k--) {
        checkmax(temp[st][ed], x[st][k] + x[k][ed]);
      }
    }
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(temp[st][ed], temp[st][ed - 1]);
    }
    for (int ed = 0; ed < m; ed++) {
      x[st][ed] = temp[st][ed];
    }
  }
}
void Bin(int K) {
  while (K) {
    if (K & 1) {
      calc_dp();
    }
    calc_x();
    K >>= 1;
  }
}
int b[N];
int main() {
  int n, T;
  scanf("%d%d", &n, &T);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b, b + n);
  m = unique(b, b + n) - b;
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(b, b + m, a[i]) - b;
  }
  memset(x, -1, sizeof x);
  x[a[0]][a[0]] = 1;
  for (int i = 1; i < n; i++) {
    for (int st = 0; st < a[i] + 1; st++) {
      for (int ed = a[i]; ed >= st; ed--) {
        if (~x[st][ed]) {
          checkmax(x[st][a[i]], x[st][ed] + 1);
        }
      }
    }
    checkmax(x[a[i]][a[i]], 1);
  }
  for (int st = 0; st < m; st++) {
    for (int ed = st + 1; ed < m; ed++) {
      checkmax(x[st][ed], x[st][ed - 1]);
    }
  }
  Bin(T);
  int answer = 0;
  for (int st = 0; st < m; st++)
    for (int ed = 0; ed < m; ed++) checkmax(answer, dp[st][ed]);
  printf("%d\n", answer);
  return 0;
}

```