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>
using namespace std;
long long int check(long long int a, long long int b, long long int c,
                    long long int d, long long int e) {
  e -= d;
  d -= c;
  c -= b;
  b -= a;
  long long int mx = max(max(b, c), max(d, e));
  long long int mi = min(min(b, c), max(d, e));
  if (mx == mi) return mx;
  return 0;
}
long long int read() {
  long long int x;
  scanf("%lld", &x);
  return x;
}
vector<long long int> ANS;
void solve(long long int n, long long int k) {
  vector<long long int> V(n * k), C;
  for (long long int i = 0; i < n; i++) V[i] = read();
  for (long long int i = n; i < V.size(); i++) V[i] = V[i - n];
  for (long long int i = 0; i < V.size(); i++) {
    if (!i)
      C.push_back(V[i]);
    else {
      long long int cur = V[i];
      long long int tmp = upper_bound(C.begin(), C.end(), cur) - C.begin();
      if (tmp == C.size())
        C.push_back(cur);
      else
        C[tmp] = cur;
    }
    if ((i + 1) % n == 0) ANS.push_back(C.size());
  }
}
int main() {
  long long int n = read(), k = read();
  solve(n, min(k, (long long int)305));
  if (k <= ANS.size())
    cout << ANS[k - 1] << endl;
  else {
    long long int det = k - ANS.size(),
                  d = ANS[ANS.size() - 1] - ANS[ANS.size() - 2];
    cout << ANS.back() + det * d << endl;
  }
}
