#include <bits/stdc++.h>
using namespace std;
const int INF = (1LL << 30) - 1;
const long long int LINF = (1LL << 62) - 1;
const int NMAX = 100;
int N, T, sol;
int A[NMAX * NMAX + 5];
int P[NMAX * NMAX + 5];
int D[NMAX * NMAX + 5];
map<int, int> Q;
vector<pair<int, int> > F;
int fr;
int main() {
  cin.sync_with_stdio(false);
  scanf("%d%d", &N, &T);
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  if (T <= N) {
    for (int i = N + 1; i <= T * N; i++) A[i] = A[i - N];
    for (int i = 1, j; i <= T * N; i++) {
      P[i] = INF;
      j = upper_bound(P + 1, P + i + 1, A[i]) - P;
      D[i] = j;
      P[j] = A[i];
      sol = max(sol, D[i]);
    }
    printf("%d\n", sol);
  } else {
    for (int i = N + 1; i <= N * N; i++) A[i] = A[i - N];
    for (int i = 1, j; i <= N * N; i++) {
      P[i] = INF;
      j = upper_bound(P + 1, P + i + 1, A[i]) - P;
      D[i] = j;
      P[j] = A[i];
      sol = max(sol, D[i]);
    }
    for (int i = 1; i <= N; i++) Q[A[i]]++;
    for (auto x : Q) F.push_back(make_pair(x.second, x.first));
    sort(F.begin(), F.end());
    fr = F.back().first;
    sol += (T - N) * fr;
    printf("%d\n", sol);
  }
  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;
const int INF = (1LL << 30) - 1;
const long long int LINF = (1LL << 62) - 1;
const int NMAX = 100;
int N, T, sol;
int A[NMAX * NMAX + 5];
int P[NMAX * NMAX + 5];
int D[NMAX * NMAX + 5];
map<int, int> Q;
vector<pair<int, int> > F;
int fr;
int main() {
  cin.sync_with_stdio(false);
  scanf("%d%d", &N, &T);
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  if (T <= N) {
    for (int i = N + 1; i <= T * N; i++) A[i] = A[i - N];
    for (int i = 1, j; i <= T * N; i++) {
      P[i] = INF;
      j = upper_bound(P + 1, P + i + 1, A[i]) - P;
      D[i] = j;
      P[j] = A[i];
      sol = max(sol, D[i]);
    }
    printf("%d\n", sol);
  } else {
    for (int i = N + 1; i <= N * N; i++) A[i] = A[i - N];
    for (int i = 1, j; i <= N * N; i++) {
      P[i] = INF;
      j = upper_bound(P + 1, P + i + 1, A[i]) - P;
      D[i] = j;
      P[j] = A[i];
      sol = max(sol, D[i]);
    }
    for (int i = 1; i <= N; i++) Q[A[i]]++;
    for (auto x : Q) F.push_back(make_pair(x.second, x.first));
    sort(F.begin(), F.end());
    fr = F.back().first;
    sol += (T - N) * fr;
    printf("%d\n", sol);
  }
  return 0;
}

```