#include <bits/stdc++.h>
using namespace std;
const char IO_MODE = 3;
inline long long ReadInt() {
  long long x = 0, s = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') s = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
inline void WriteInt(long long x) {
  char c[20];
  if (!x) {
    putchar('0');
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int i = 0;
  while (x > 0) c[++i] = x % 10, x /= 10;
  while (i) putchar(c[i--] + 48);
}
template <typename T>
inline void out(T x) {
  if (IO_MODE & 1)
    WriteInt(x);
  else if (typeid(x) == typeid(int))
    printf("%i", x);
  else
    printf("%lld", (long long)x);
}
template <typename T, typename... Args>
inline void out(T x, Args... args) {
  out(x);
  putc(' ', stdout);
  out(args...);
}
template <typename T>
inline void in(T &x) {
  if (IO_MODE & 2)
    x = ReadInt();
  else if (typeid(x) == typeid(int))
    scanf("%i", &x);
  else if (typeid(x) == typeid(long long))
    scanf("%lld", &x);
}
template <typename T, typename... Args>
inline void in(T &x, Args &...args) {
  in(x);
  in(args...);
}
int aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, mm, nn, oo, pp, qq, rr, ss, tt,
    uu, vv, ww, xx, yy, zz;
int tc;
int n, t;
int A[111 * 111], L[111 * 111], R[111 * 111], Dp1[111 * 111], Dp2[111 * 111],
    cnt[111 * 111];
int main() {
  in(n, t);
  int N = n * n;
  for (int i = 0; i < n; i++) in(A[i]), cnt[A[i]]++;
  for (int i = n; i < N; i++) A[i] = A[i - n];
  for (int i = 0, len = 0; i < N; i++) {
    int p = upper_bound(L, L + len, A[i]) - L;
    L[p] = A[i];
    if (len == p) len++;
    Dp1[i] = p + 1;
  }
  for (int i = N, len = 0; i--;) {
    int p = upper_bound(R, R + len, A[i], greater<int>()) - R;
    R[p] = A[i];
    if (len == p) len++;
    Dp2[i] = p + 1;
  }
  long long ans = 0;
  if (t <= n)
    ans = *max_element(Dp1, Dp1 + t * n);
  else if (t <= 2 * n) {
    int x = t - n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (A[j] >= A[i])
          ans = max(ans, (long long)Dp1[N - n + i] + Dp2[N - x * n + j]);
  } else {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (A[j] >= A[i])
          ans = max(ans, Dp1[N - n + i] + (long long)(t - 2 * n) * cnt[A[i]] +
                             Dp2[j]);
  }
  cout << ans << endl;
}

### Prompt

Please formulate 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 char IO_MODE = 3;
inline long long ReadInt() {
  long long x = 0, s = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') s = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
inline void WriteInt(long long x) {
  char c[20];
  if (!x) {
    putchar('0');
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int i = 0;
  while (x > 0) c[++i] = x % 10, x /= 10;
  while (i) putchar(c[i--] + 48);
}
template <typename T>
inline void out(T x) {
  if (IO_MODE & 1)
    WriteInt(x);
  else if (typeid(x) == typeid(int))
    printf("%i", x);
  else
    printf("%lld", (long long)x);
}
template <typename T, typename... Args>
inline void out(T x, Args... args) {
  out(x);
  putc(' ', stdout);
  out(args...);
}
template <typename T>
inline void in(T &x) {
  if (IO_MODE & 2)
    x = ReadInt();
  else if (typeid(x) == typeid(int))
    scanf("%i", &x);
  else if (typeid(x) == typeid(long long))
    scanf("%lld", &x);
}
template <typename T, typename... Args>
inline void in(T &x, Args &...args) {
  in(x);
  in(args...);
}
int aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, mm, nn, oo, pp, qq, rr, ss, tt,
    uu, vv, ww, xx, yy, zz;
int tc;
int n, t;
int A[111 * 111], L[111 * 111], R[111 * 111], Dp1[111 * 111], Dp2[111 * 111],
    cnt[111 * 111];
int main() {
  in(n, t);
  int N = n * n;
  for (int i = 0; i < n; i++) in(A[i]), cnt[A[i]]++;
  for (int i = n; i < N; i++) A[i] = A[i - n];
  for (int i = 0, len = 0; i < N; i++) {
    int p = upper_bound(L, L + len, A[i]) - L;
    L[p] = A[i];
    if (len == p) len++;
    Dp1[i] = p + 1;
  }
  for (int i = N, len = 0; i--;) {
    int p = upper_bound(R, R + len, A[i], greater<int>()) - R;
    R[p] = A[i];
    if (len == p) len++;
    Dp2[i] = p + 1;
  }
  long long ans = 0;
  if (t <= n)
    ans = *max_element(Dp1, Dp1 + t * n);
  else if (t <= 2 * n) {
    int x = t - n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (A[j] >= A[i])
          ans = max(ans, (long long)Dp1[N - n + i] + Dp2[N - x * n + j]);
  } else {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (A[j] >= A[i])
          ans = max(ans, Dp1[N - n + i] + (long long)(t - 2 * n) * cnt[A[i]] +
                             Dp2[j]);
  }
  cout << ans << endl;
}

```