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 n, t;
int a[200];
int li[10200];
vector<pair<int, int> > lis[10200];
int main() {
  scanf("%d%d", &n, &t);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  fill(li, li + 10200, 1e9);
  int i = 0;
  int *it;
  int cur;
  int mx = 0;
  li[0] = 0;
  while (i < n * t) {
    cur = a[i % n];
    it = upper_bound(li, li + 10200, cur);
    int l = it - li;
    li[l] = cur;
    mx = max(mx, l);
    lis[l].push_back(make_pair(i, lis[l - 1].size() - 1));
    if (i / n == 100 && i % n == n - 1) break;
    i++;
  }
  if (i == n * t) return cout << mx << endl, 0;
  bool vis[200];
  int ans = 0;
  fill(vis, vis + 200, 0);
  vector<int> curv;
  int j = lis[mx].size() - 1;
  for (int i = mx; i > 0; i--) {
    curv.push_back(lis[i][j].first);
    j = lis[i][j].second;
  }
  reverse(curv.begin(), curv.end());
  for (int k = 0; k < curv.size(); k++) {
    int cur = curv[k];
    if (vis[cur % n]) {
      for (int lte = curv.size() - 1; lte > -1; lte--) {
        int cte = curv[lte];
        if (cte % n == cur % n) {
          ans = curv.size() - lte + k;
          int m = (lte - k) / ((cte - cur) / n);
          cte = n * t - (101 * n - cte);
          ans += (-cur + cte) / n * m;
          printf("%d", ans);
          return 0;
        }
      }
    }
    vis[cur % n] = true;
  }
}
