#include <bits/stdc++.h>
using namespace std;
int tu[10001];
int dp[10001];
int tt[101];
int hs[301];
int main() {
  int n, t;
  cin >> n >> t;
  int qq = min(t, n);
  for (int a = 1; a <= n; a++) cin >> tt[a];
  for (int a = 1; a <= qq; a++)
    for (int b = 1; b <= n; b++) tu[b + (a - 1) * n] = tt[b];
  int xc = n * qq;
  dp[1] = tu[1];
  int cc = 1;
  int dd = tu[1];
  for (int a = 2; a <= xc; a++) {
    if (tu[a] >= dd) {
      dp[++cc] = tu[a];
      dd = dp[cc];
      continue;
    }
    int wew = upper_bound(dp + 1, dp + cc + 1, tu[a]) - dp;
    dp[wew] = tu[a];
    dd = dp[cc];
  }
  int wew = 0;
  for (int a = 1; a <= n; a++) hs[tt[a]]++;
  int gs = 0;
  for (int a = 1; a <= 300; a++) gs = max(gs, hs[a]);
  if (t > n) cc += gs * (t - n);
  cout << cc << 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;
int tu[10001];
int dp[10001];
int tt[101];
int hs[301];
int main() {
  int n, t;
  cin >> n >> t;
  int qq = min(t, n);
  for (int a = 1; a <= n; a++) cin >> tt[a];
  for (int a = 1; a <= qq; a++)
    for (int b = 1; b <= n; b++) tu[b + (a - 1) * n] = tt[b];
  int xc = n * qq;
  dp[1] = tu[1];
  int cc = 1;
  int dd = tu[1];
  for (int a = 2; a <= xc; a++) {
    if (tu[a] >= dd) {
      dp[++cc] = tu[a];
      dd = dp[cc];
      continue;
    }
    int wew = upper_bound(dp + 1, dp + cc + 1, tu[a]) - dp;
    dp[wew] = tu[a];
    dd = dp[cc];
  }
  int wew = 0;
  for (int a = 1; a <= n; a++) hs[tt[a]]++;
  int gs = 0;
  for (int a = 1; a <= 300; a++) gs = max(gs, hs[a]);
  if (t > n) cc += gs * (t - n);
  cout << cc << endl;
  return 0;
}

```