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;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, t;
  cin >> n >> t;
  vector<int> a(n);
  for (int& ai : a) cin >> ai;
  auto build = [&](int t) {
    vector<int> ret;
    while (t--) {
      ret.insert(end(ret), begin(a), end(a));
    }
    return ret;
  };
  const int INF = 1e9;
  auto get_list = [&](const vector<int>& a) {
    vector<int> lis(int(a.size()), 1);
    vector<int> dp(int(a.size()) + 1, INF);
    dp[0] = -1;
    for (int i = 0; i < int(a.size()); i++) {
      lis[i] = upper_bound(begin(dp), end(dp), a[i]) - begin(dp);
      dp[lis[i]] = a[i];
    }
    return lis;
  };
  if (t <= 2 * n) {
    vector<int> dp = get_list(build(t));
    cout << *max_element(begin(dp), end(dp)) << '\n';
    return (0);
  }
  vector<int> x = build(n);
  vector<int> dp1 = get_list(x);
  for (int& xi : x) xi = INF - xi;
  reverse(begin(x), end(x));
  vector<int> dp2 = get_list(x);
  reverse(begin(dp2), end(dp2));
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++) {
      if (a[i] == a[j]) cnt++;
    }
    for (int j = 0; j < n; j++) {
      if (a[j] < a[i]) continue;
      ans = max(ans, dp1[(n - 1) * n + i] + cnt * (t - 2 * n) + dp2[j]);
    }
  }
  cout << ans << '\n';
  return (0);
}
