#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
const long long MOD = 1e9 + 696969;
const long long INF = 1e18;
int n, m, k, a, b, c, p, q;
long long N, M, A, B, C, P, Q;
int T;
int t[101010], dp[101010];
int licz[101010];
int dr[1337];
void add(int p, int v) {
  for (; p < 1300; p += p & (-p)) dr[p] = max(dr[p], v);
}
int get(int p) {
  int s = 0;
  for (; p > 0; p -= p & (-p)) s = max(s, dr[p]);
  return s;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> T;
  for (int i = 1; i <= n; ++i) cin >> t[i], licz[t[i]]++;
  int reszta = T - n;
  if (T > n) T = n;
  {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j < T; ++j) t[i + j * n] = t[i];
  }
  int all = T * n;
  for (int i = 1; i <= all; ++i) {
    int help = get(t[i]) + 1;
    dp[i] = help;
    add(t[i], help);
  }
  int WYN = 0;
  for (int i = 1; i <= all; ++i) WYN = max(WYN, dp[i]);
  int maxlicz = 0;
  for (int i = 0; i < 400; ++i) maxlicz = max(licz[i], maxlicz);
  if (reszta > 0) WYN += maxlicz * reszta;
  cout << WYN;
}

### Prompt

Generate 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 mod = 1e9 + 7;
const int inf = 1e9 + 9;
const long long MOD = 1e9 + 696969;
const long long INF = 1e18;
int n, m, k, a, b, c, p, q;
long long N, M, A, B, C, P, Q;
int T;
int t[101010], dp[101010];
int licz[101010];
int dr[1337];
void add(int p, int v) {
  for (; p < 1300; p += p & (-p)) dr[p] = max(dr[p], v);
}
int get(int p) {
  int s = 0;
  for (; p > 0; p -= p & (-p)) s = max(s, dr[p]);
  return s;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> T;
  for (int i = 1; i <= n; ++i) cin >> t[i], licz[t[i]]++;
  int reszta = T - n;
  if (T > n) T = n;
  {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j < T; ++j) t[i + j * n] = t[i];
  }
  int all = T * n;
  for (int i = 1; i <= all; ++i) {
    int help = get(t[i]) + 1;
    dp[i] = help;
    add(t[i], help);
  }
  int WYN = 0;
  for (int i = 1; i <= all; ++i) WYN = max(WYN, dp[i]);
  int maxlicz = 0;
  for (int i = 0; i < 400; ++i) maxlicz = max(licz[i], maxlicz);
  if (reszta > 0) WYN += maxlicz * reszta;
  cout << WYN;
}

```