#include <bits/stdc++.h>
char _bf[1048576];
char *__p1 = _bf, *__p2 = _bf;
template <class T>
void PRT(const T a) {
  if (a < 0) {
    putchar(45), PRT(-a);
    return;
  }
  if (a >= 10) PRT(a / 10);
  putchar(a % 10 + 48);
}
template <class T>
void UPRT(const T a) {
  if (a >= 10) UPRT(a / 10);
  putchar(a % 10 + 48);
}
constexpr int MN(10003);
int a[MN];
void multi(int &n, const int T) {
  int i, k, *p;
  for (k = 1, p = a; k < T; ++k)
    for (p += n, i = 0; i < n; ++i) p[i] = a[i];
  n *= T;
}
int LIS(const int n) {
  int sta[MN], top = 0;
  sta[top++] = *a;
  for (int i = 1; i < n; ++i) {
    if (a[i] >= sta[top - 1])
      sta[top++] = a[i];
    else
      *std::upper_bound(sta, sta + top, a[i]) = a[i];
  }
  return top;
}
int main() {
  char *_p1 = __p1, *_p2 = __p2;
  int n, T;
  {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (n = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         n = (n << 1) + (n << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) n = -n;
  }
  {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (T = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         T = (T << 1) + (T << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) T = -T;
  }
  int i, k, *p;
  for (i = 0; i < n; ++i) {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (a[i] = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         a[i] = (a[i] << 1) + (a[i] << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) a[i] = -a[i];
  }
  if (T > n) {
    int hs[303] = {0};
    for (int i = 0; i < n; ++i) ++hs[a[i]];
    int max_cnt = 0;
    for (int i = 1; i <= 300; ++i)
      if (hs[i] > max_cnt) max_cnt = hs[i];
    int ans = (T - n) * max_cnt;
    multi(n, n);
    ans += LIS(n);
    UPRT(ans);
  } else {
    multi(n, T);
    UPRT(LIS(n));
  }
  return 0;
}

### 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>
char _bf[1048576];
char *__p1 = _bf, *__p2 = _bf;
template <class T>
void PRT(const T a) {
  if (a < 0) {
    putchar(45), PRT(-a);
    return;
  }
  if (a >= 10) PRT(a / 10);
  putchar(a % 10 + 48);
}
template <class T>
void UPRT(const T a) {
  if (a >= 10) UPRT(a / 10);
  putchar(a % 10 + 48);
}
constexpr int MN(10003);
int a[MN];
void multi(int &n, const int T) {
  int i, k, *p;
  for (k = 1, p = a; k < T; ++k)
    for (p += n, i = 0; i < n; ++i) p[i] = a[i];
  n *= T;
}
int LIS(const int n) {
  int sta[MN], top = 0;
  sta[top++] = *a;
  for (int i = 1; i < n; ++i) {
    if (a[i] >= sta[top - 1])
      sta[top++] = a[i];
    else
      *std::upper_bound(sta, sta + top, a[i]) = a[i];
  }
  return top;
}
int main() {
  char *_p1 = __p1, *_p2 = __p2;
  int n, T;
  {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (n = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         n = (n << 1) + (n << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) n = -n;
  }
  {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (T = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         T = (T << 1) + (T << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) T = -T;
  }
  int i, k, *p;
  for (i = 0; i < n; ++i) {
    register char _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) +
                                             fread(_bf, 1, 1048576, stdin),
                                       _p1 == _p2)
                            ? EOF
                            : *_p1++),
                  _v = 1;
    for (a[i] = 0; _c < 48 || _c > 57;
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         a[i] = (a[i] << 1) + (a[i] << 3) + _c - 48,
         _c = (_p1 == _p2 && (_p2 = (_p1 = _bf) + fread(_bf, 1, 1048576, stdin),
                             _p1 == _p2)
                   ? EOF
                   : *_p1++))
      ;
    if (_v == -1) a[i] = -a[i];
  }
  if (T > n) {
    int hs[303] = {0};
    for (int i = 0; i < n; ++i) ++hs[a[i]];
    int max_cnt = 0;
    for (int i = 1; i <= 300; ++i)
      if (hs[i] > max_cnt) max_cnt = hs[i];
    int ans = (T - n) * max_cnt;
    multi(n, n);
    ans += LIS(n);
    UPRT(ans);
  } else {
    multi(n, T);
    UPRT(LIS(n));
  }
  return 0;
}

```