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;
void solve() {
  int n, t;
  cin >> n >> t;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  vector<int> b = a;
  sort(b.begin(), b.end());
  int cup = 0, cur = 1, pos = 0;
  for (int i = 1; i < b.size(); ++i) {
    if (b[i - 1] == b[i]) {
      cur += 1;
    } else {
      cup = max(cup, cur);
      cur = 1;
      pos = i;
    }
  }
  cup = max(cup, cur);
  int minus = min((2 * n + 5), t);
  for (int i = 0; i < minus - 1; ++i) {
    for (int j = 0; j < n; ++j) {
      a.push_back(a[j]);
    }
  }
  t -= minus;
  int inf = 1000 * 1000 * 1000 + 7;
  vector<int> d(a.size() + 1);
  for (int i = 1; i < d.size(); ++i) d[i] = inf;
  d[0] = -1;
  for (int i = 0; i < a.size(); i++) {
    int j = int(upper_bound(d.begin(), d.end(), a[i]) - d.begin());
    if (d[j - 1] <= a[i] && a[i] < d[j]) {
      d[j] = a[i];
    }
  }
  int r = 0;
  for (int i = 0; i < d.size(); ++i) {
    if (d[i] != inf) {
      r = i;
    }
  }
  if (t > 0) {
    r += cup * t;
  }
  cout << r;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}
