#include <bits/stdc++.h>
using namespace std;
int CeilIndex(int A[], int l, int r, int key) {
  int m;
  while (r - l > 1) {
    m = l + (r - l) / 2;
    (A[m] > key ? r : l) = m;
  }
  return r;
}
int LongestIncreasingSubsequenceLength(int A[], int size) {
  int *tailTable = new int[size];
  int len;
  memset(tailTable, 0, sizeof(tailTable[0]) * size);
  tailTable[0] = A[0];
  len = 1;
  for (int i = 1; i < size; i++) {
    if (A[i] < tailTable[0])
      tailTable[0] = A[i];
    else if (A[i] >= tailTable[len - 1])
      tailTable[len++] = A[i];
    else
      tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
  }
  delete[] tailTable;
  return len;
}
int br[50000];
void solve() {
  int n, t;
  cin >> n >> t;
  int ar[n];
  map<int, int> mm;
  for (int i = 0; i < (int)(n); i++) {
    cin >> ar[i];
    mm[ar[i]]++;
  }
  int aa = 0;
  if (t <= 3 * n) {
    int ind = 0;
    for (int i = 0; i < t; i++) {
      for (int j = 0; j < n; j++) {
        br[ind++] = ar[j];
      }
    }
    aa = LongestIncreasingSubsequenceLength(br, ind);
  } else {
    for (auto itr = mm.begin(); itr != mm.end(); itr++) {
      int z = itr->first;
      int freq = itr->second;
      int ans = 0;
      int ind = 0;
      for (int j = 0; j < n + 1; j++) {
        for (int i = 0; i < n; i++) {
          if (ar[i] <= z) {
            br[ind++] = ar[i];
          }
        }
      }
      ans += LongestIncreasingSubsequenceLength(br, ind);
      ind = 0;
      for (int j = 0; j < n + 1; j++) {
        for (int i = 0; i < n; i++) {
          if (ar[i] >= z) {
            br[ind++] = ar[i];
          }
        }
      }
      ans += LongestIncreasingSubsequenceLength(br, ind);
      ans += (t - n - n - 2) * freq;
      aa = max(ans, aa);
    }
  }
  cout << aa;
}
int main() {
  cin.sync_with_stdio(0);
  cout.sync_with_stdio(0);
  int TC = 1;
  for (int ZZ = 1; ZZ <= TC; ZZ++) {
    solve();
  }
  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>
using namespace std;
int CeilIndex(int A[], int l, int r, int key) {
  int m;
  while (r - l > 1) {
    m = l + (r - l) / 2;
    (A[m] > key ? r : l) = m;
  }
  return r;
}
int LongestIncreasingSubsequenceLength(int A[], int size) {
  int *tailTable = new int[size];
  int len;
  memset(tailTable, 0, sizeof(tailTable[0]) * size);
  tailTable[0] = A[0];
  len = 1;
  for (int i = 1; i < size; i++) {
    if (A[i] < tailTable[0])
      tailTable[0] = A[i];
    else if (A[i] >= tailTable[len - 1])
      tailTable[len++] = A[i];
    else
      tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
  }
  delete[] tailTable;
  return len;
}
int br[50000];
void solve() {
  int n, t;
  cin >> n >> t;
  int ar[n];
  map<int, int> mm;
  for (int i = 0; i < (int)(n); i++) {
    cin >> ar[i];
    mm[ar[i]]++;
  }
  int aa = 0;
  if (t <= 3 * n) {
    int ind = 0;
    for (int i = 0; i < t; i++) {
      for (int j = 0; j < n; j++) {
        br[ind++] = ar[j];
      }
    }
    aa = LongestIncreasingSubsequenceLength(br, ind);
  } else {
    for (auto itr = mm.begin(); itr != mm.end(); itr++) {
      int z = itr->first;
      int freq = itr->second;
      int ans = 0;
      int ind = 0;
      for (int j = 0; j < n + 1; j++) {
        for (int i = 0; i < n; i++) {
          if (ar[i] <= z) {
            br[ind++] = ar[i];
          }
        }
      }
      ans += LongestIncreasingSubsequenceLength(br, ind);
      ind = 0;
      for (int j = 0; j < n + 1; j++) {
        for (int i = 0; i < n; i++) {
          if (ar[i] >= z) {
            br[ind++] = ar[i];
          }
        }
      }
      ans += LongestIncreasingSubsequenceLength(br, ind);
      ans += (t - n - n - 2) * freq;
      aa = max(ans, aa);
    }
  }
  cout << aa;
}
int main() {
  cin.sync_with_stdio(0);
  cout.sync_with_stdio(0);
  int TC = 1;
  for (int ZZ = 1; ZZ <= TC; ZZ++) {
    solve();
  }
  return 0;
}

```