#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 500, MOD = 1e9 + 7;
int BIT[505], A[MAX], F[MAX], DP[MAX];
int AUX[30 * MAX];
int N, T;
inline void update(int idx, int val) {
  while (idx <= 500) {
    BIT[idx] = max(BIT[idx], val);
    idx += idx & -idx;
  }
}
inline int query(int idx) {
  int res = 0;
  while (idx >= 1) {
    res = max(res, BIT[idx]);
    idx -= idx & -idx;
  }
  return res;
}
int main() {
  cin.tie(0), ios::sync_with_stdio(0);
  cin >> N >> T;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    F[A[i]]++;
  }
  if (T <= (N << 1)) {
    int ans = 0;
    while (T--) {
      for (int i = 1; i <= N; ++i) {
        int x = query(A[i]) + 1;
        ans = max(ans, x);
        update(A[i], x);
      }
    }
    cout << ans << endl;
  } else {
    for (int i = 0; i < N; i++)
      for (int j = 1; j <= N; j++) AUX[i * N + j] = A[j];
    T -= (N << 1);
    for (int i = 1; i <= N * N; i++) {
      int val = 0;
      for (int j = 1; j <= AUX[i]; j++) val = max(val, DP[j]);
      DP[AUX[i]] = val + 1;
    }
    long long inc = 0;
    int temp = 0;
    for (int i = 0; i <= 400; i++) {
      temp = max(temp, DP[i]);
      DP[i] = temp + T * F[i];
    }
    for (int i = 1; i <= N * N; i++) {
      int v = 0;
      for (int j = 1; j <= AUX[i]; j++) v = max(v, DP[j]);
      DP[AUX[i]] = v + 1;
    }
    int res = 0;
    for (int i = 0; i <= 400; i++) res = max(res, DP[i]);
    cout << res << endl;
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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 MAX = 2e5 + 500, MOD = 1e9 + 7;
int BIT[505], A[MAX], F[MAX], DP[MAX];
int AUX[30 * MAX];
int N, T;
inline void update(int idx, int val) {
  while (idx <= 500) {
    BIT[idx] = max(BIT[idx], val);
    idx += idx & -idx;
  }
}
inline int query(int idx) {
  int res = 0;
  while (idx >= 1) {
    res = max(res, BIT[idx]);
    idx -= idx & -idx;
  }
  return res;
}
int main() {
  cin.tie(0), ios::sync_with_stdio(0);
  cin >> N >> T;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    F[A[i]]++;
  }
  if (T <= (N << 1)) {
    int ans = 0;
    while (T--) {
      for (int i = 1; i <= N; ++i) {
        int x = query(A[i]) + 1;
        ans = max(ans, x);
        update(A[i], x);
      }
    }
    cout << ans << endl;
  } else {
    for (int i = 0; i < N; i++)
      for (int j = 1; j <= N; j++) AUX[i * N + j] = A[j];
    T -= (N << 1);
    for (int i = 1; i <= N * N; i++) {
      int val = 0;
      for (int j = 1; j <= AUX[i]; j++) val = max(val, DP[j]);
      DP[AUX[i]] = val + 1;
    }
    long long inc = 0;
    int temp = 0;
    for (int i = 0; i <= 400; i++) {
      temp = max(temp, DP[i]);
      DP[i] = temp + T * F[i];
    }
    for (int i = 1; i <= N * N; i++) {
      int v = 0;
      for (int j = 1; j <= AUX[i]; j++) v = max(v, DP[j]);
      DP[AUX[i]] = v + 1;
    }
    int res = 0;
    for (int i = 0; i <= 400; i++) res = max(res, DP[i]);
    cout << res << endl;
  }
  return 0;
}

```