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. 
#include <bits/stdc++.h>
template <typename T>
void UpdateMin(T& a, const T b) {
  a = std::min(a, b);
}
template <typename T>
void UpdateMax(T& a, const T b) {
  a = std::max(a, b);
}
static const long double Eps = 1.0e-09;
template <typename T>
bool IsEqual(const T a, const T b) {
  return std::abs(a - b) < Eps;
}
template <typename T>
bool IsGreater(const T a, const T b) {
  return a > b + Eps;
}
template <typename T>
bool IsLess(const T a, const T b) {
  return a + Eps < b;
}
template <typename T>
std::string ToStr(const T& val) {
  std::ostringstream ostr;
  ostr << val;
  return ostr.str();
}
template <typename T>
bool FromStr(const std::string& str, T& val) {
  std::istringstream istr(str);
  istr >> val;
  return !!istr;
}
template <typename T>
std::istream& operator>>(std::istream& ist, std::vector<T>& data) {
  ;
  for (size_t i = 0; i < data.size(); i++) {
    ist >> data[i];
  }
  return ist;
}
template <typename T>
T Read(std::istream& ist) {
  ;
  T val;
  ist >> val;
  return val;
}
template <typename T>
std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data) {
  for (size_t i = 0; i < data.size(); i++) {
    if (i != 0) {
      ost << ' ';
    }
    ost << data[i];
  }
  return ost;
}
template <size_t id>
class StopWatch {};
size_t GetMaxLength(const std::vector<int32_t>& a) {
  const int32_t PINF = std::numeric_limits<int32_t>::max();
  const int32_t MINF = std::numeric_limits<int32_t>::min();
  const size_t n = a.size();
  std::vector<int32_t> d(n + 1);
  d[0] = MINF;
  for (size_t i = 1; i < d.size(); ++i) {
    d[i] = PINF;
  }
  for (size_t i = 0; i < n; i++) {
    const int32_t v = a[i];
    const size_t j =
        std::distance(d.begin(), std::upper_bound(d.begin(), d.end(), v));
    if ((d[j - 1] <= v) && (v < d[j])) {
      d[j] = v;
    }
  }
  size_t ans = 0;
  for (size_t i = 0; i < d.size(); i++) {
    if (d[i] != PINF) {
      ans = i;
    }
  }
  return ans;
}
bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode) {
  StopWatch<1> sw;
  (void)sw;
  size_t n;
  ist >> n;
  if (multipleTestMode && !ist) return false;
  uint64_t t;
  ist >> t;
  std::vector<int32_t> a(n);
  ist >> a;
  std::map<int32_t, size_t> c;
  for (size_t i = 0; i < a.size(); i++) {
    c[a[i]] += 1;
  }
  const uint64_t limit = 5000;
  const uint64_t mult = std::min(t, limit);
  std::vector<int32_t> b;
  for (size_t i = 0; i < mult; i++) {
    b.insert(b.end(), a.begin(), a.end());
  }
  uint64_t ans = GetMaxLength(b);
  if (t > limit) {
    b.insert(b.end(), a.begin(), a.end());
    const uint64_t nextAns = GetMaxLength(b);
    const uint64_t d = nextAns - ans;
    ans += (t - limit) * d;
  }
  ost << ans << std::endl;
  return multipleTestMode;
}
int main(int argc, const char* argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::istream* ist = &std::cin;
  std::ostream* ost = &std::cout;
  std::unique_ptr<std::istream> fileInput;
  if (argc > 1) {
    fileInput.reset(new std::ifstream(argv[1]));
    if (!(*fileInput)) {
      std::cout << "File not found: " << argv[1] << std::endl;
    }
    ist = fileInput.get();
  }
  Solve(*ist, *ost, false);
}
