#include <bits/stdc++.h>
const int MAX = 1e6 + 11;
using namespace std;
const int INF = (int const)(1e9);
static vector<int> build(int T, int N, int *A) {
  vector<int> res;
  for (int i = 0; i < T; ++i) {
    for (int j = 0; j < N; ++j) {
      res.push_back(A[j]);
    }
  }
  return res;
}
static vector<int> dp(vector<int> A) {
  vector<int> D(A.size() + 5, INF);
  D[0] = -INF;
  vector<int> res(A.size());
  for (int i = 0; i < A.size(); ++i) {
    int idx = (int)(upper_bound(D.begin(), D.end(), A[i]) - D.begin());
    if (D[idx - 1] <= A[i] && A[i] < D[idx]) {
      D[idx] = A[i];
      res[i] = idx;
    }
  }
  return res;
}
int N, T, A[MAX], C[MAX];
int main() {
  scanf("%d %d", &N, &T);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
    C[A[i]]++;
  }
  if (T * N < MAX) {
    auto d = dp(build(T, N, A));
    int res = 0;
    for (int i = 0; i < d.size(); ++i) {
      res = max(res, d[i]);
    }
    printf("%d", res);
    return 0;
  }
  auto b = build(N, N, A);
  auto e = build(N, N, A);
  for (int i = 0; i < e.size(); ++i) e[i] = INF - e[i];
  reverse(e.begin(), e.end());
  auto d1 = dp(b);
  auto d2 = dp(e);
  reverse(d2.begin(), d2.end());
  int res = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (A[j] >= A[i]) {
        res = max(res, d1[N * (N - 1) + i] + d2[j] + (T - 2 * N) * C[A[i]]);
      }
    }
  }
  printf("%d", res);
  return 0;
}

### 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>
const int MAX = 1e6 + 11;
using namespace std;
const int INF = (int const)(1e9);
static vector<int> build(int T, int N, int *A) {
  vector<int> res;
  for (int i = 0; i < T; ++i) {
    for (int j = 0; j < N; ++j) {
      res.push_back(A[j]);
    }
  }
  return res;
}
static vector<int> dp(vector<int> A) {
  vector<int> D(A.size() + 5, INF);
  D[0] = -INF;
  vector<int> res(A.size());
  for (int i = 0; i < A.size(); ++i) {
    int idx = (int)(upper_bound(D.begin(), D.end(), A[i]) - D.begin());
    if (D[idx - 1] <= A[i] && A[i] < D[idx]) {
      D[idx] = A[i];
      res[i] = idx;
    }
  }
  return res;
}
int N, T, A[MAX], C[MAX];
int main() {
  scanf("%d %d", &N, &T);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
    C[A[i]]++;
  }
  if (T * N < MAX) {
    auto d = dp(build(T, N, A));
    int res = 0;
    for (int i = 0; i < d.size(); ++i) {
      res = max(res, d[i]);
    }
    printf("%d", res);
    return 0;
  }
  auto b = build(N, N, A);
  auto e = build(N, N, A);
  for (int i = 0; i < e.size(); ++i) e[i] = INF - e[i];
  reverse(e.begin(), e.end());
  auto d1 = dp(b);
  auto d2 = dp(e);
  reverse(d2.begin(), d2.end());
  int res = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (A[j] >= A[i]) {
        res = max(res, d1[N * (N - 1) + i] + d2[j] + (T - 2 * N) * C[A[i]]);
      }
    }
  }
  printf("%d", res);
  return 0;
}

```