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;
const int MN = 111;
int a[MN], n, g[MN][MN], c[MN];
struct Block {
  int f[MN][MN];
  void cal1() {
    memset(f, 0, sizeof f);
    for (int from = (1), _b = (100); from <= _b; from++) {
      for (int to = (from), _b = (100); to <= _b; to++) f[from][to] = 0;
      memset(g, 0, sizeof g);
      for (int i = (1), _b = (n); i <= _b; i++) {
        for (int to = (from), _b = (100); to <= _b; to++)
          g[i][to] = g[i - 1][to];
        if (a[i] >= from) {
          g[i][a[i]] = max(g[i][a[i]], 1);
          for (int prev = (from), _b = (a[i]); prev <= _b; prev++)
            g[i][a[i]] = max(g[i][a[i]], g[i - 1][prev] + 1);
        }
      }
      for (int to = (from), _b = (100); to <= _b; to++) f[from][to] = g[n][to];
    }
  }
  void print() {
    for (int from = (1), _b = (4); from <= _b; from++) {
      for (int to = (1), _b = (4); to <= _b; to++) cout << f[from][to] << ' ';
      cout << endl;
    }
    cout << "----" << endl;
  }
} f[30], trans;
Block operator+(const Block& a, const Block& b) {
  Block res;
  memset(res.f, 0, sizeof res.f);
  for (int from = (1), _b = (100); from <= _b; from++) {
    for (int to = (1), _b = (100); to <= _b; to++) {
      res.f[from][to] = a.f[from][to];
      for (int mid = (from), _b = (to); mid <= _b; mid++)
        res.f[from][to] = max(res.f[from][to], a.f[from][mid] + b.f[mid][to]);
    }
  }
  return res;
}
void RR() {
  for (int i = (1), _b = (n); i <= _b; i++) c[i] = a[i];
  sort(c + 1, c + n + 1);
  int sc = unique(c + 1, c + n + 1) - c - 1;
  for (int i = (1), _b = (n); i <= _b; i++)
    a[i] = lower_bound(c + 1, c + n + 1, a[i]) - c;
}
int main() {
  ios ::sync_with_stdio(false);
  int T;
  while (cin >> n >> T) {
    for (int i = (1), _b = (n); i <= _b; i++) cin >> a[i];
    RR();
    f[0].cal1();
    for (int i = (1), _b = (23); i <= _b; i++) f[i] = f[i - 1] + f[i - 1];
    bool first = true;
    for (int bit = 0, _a = (24); bit < _a; bit++)
      if ((T >> bit) & 1) {
        if (first) {
          first = false;
          trans = f[bit];
        } else
          trans = trans + f[bit];
      }
    int res = 0;
    for (int from = (1), _b = (100); from <= _b; from++)
      for (int to = (from), _b = (100); to <= _b; to++) {
        res = max(res, trans.f[from][to]);
        if (res == 8) {
          cout << from << ' ' << to << endl;
          assert(0);
        }
      }
    cout << res << endl;
  }
}
