#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const long long Mll = 1000000000000000000;
const int Mint = 1000000000;
struct cnt {
  long long kl, pr;
  cnt() : kl(0), pr(0) {}
  cnt(long long x, long long y) : kl(x), pr(y) {}
};
long long a[200], n, nm;
vector<cnt> b, p, e;
vector<long long> c;
vector<vector<long long> > q;
void modifu(int v, cnt x) {
  if (v == 0 || b[v].kl > x.kl) return;
  b[v] = x;
  modifu(v / 2, x);
}
cnt sn;
void find(int v, int l, int r, int l1, int r1) {
  if (l > r1 || r < l1) return;
  if (l >= l1 && r <= r1) {
    if (sn.kl < b[v].kl) sn = b[v];
    return;
  }
  find(v * 2, l, (l + r) / 2, l1, r1);
  find(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1);
}
void solv(int t) {
  for (int i(0); i < t; i++)
    for (int j(0); j < n; j++) c.push_back(a[j]);
  p.resize(c.size());
  b.resize(3 * nm);
  for (int i(0); i < c.size(); i++) {
    sn = cnt(0, 0);
    find(1, 1, nm, 1, c[i]);
    if (sn.kl == 0 && sn.pr == 0) sn.pr = -1;
    sn.kl++;
    p[i] = sn;
    sn.pr = i;
    modifu(nm + c[i] - 1, sn);
  }
}
bool check(int x, int y) {
  if (q[x].size() != q[y].size()) return false;
  for (int i(0); i < q[x].size(); i++)
    if (q[x][i] != q[y][i]) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  int t;
  cin >> n >> t;
  for (int i(0); i < n; i++) cin >> a[i];
  nm = 1;
  while (nm < 310) nm = nm * 2;
  if (t <= 400) {
    solv(t);
    long long ans = 0;
    for (int i(0); i < p.size(); i++)
      if (p[i].kl > ans) ans = p[i].kl;
    cout << ans;
    return 0;
  }
  solv(400);
  q.resize(500);
  long long v = 0, ns = 0;
  for (int i(0); i < p.size(); i++)
    if (p[i].kl > ns) {
      ns = p[i].kl;
      v = i;
    }
  while (v != -1) {
    int g = v / n;
    q[g].push_back(c[v]);
    v = p[v].pr;
  }
  long long ans = 0;
  ans = q[0].size();
  int j = 1;
  while (!check(j, j + 1)) {
    ans += q[j].size();
    j++;
  }
  int r = 399;
  ans += q[r].size();
  r--;
  int k = 1;
  while (!check(r, r + 1)) {
    ans += q[r].size();
    r--;
    k++;
  }
  long long kol = t - (k + j);
  ans = ans + kol * (q[j].size());
  cout << ans;
}

### Prompt

Create a solution in CPP for the following problem:

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. 

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const long long Mll = 1000000000000000000;
const int Mint = 1000000000;
struct cnt {
  long long kl, pr;
  cnt() : kl(0), pr(0) {}
  cnt(long long x, long long y) : kl(x), pr(y) {}
};
long long a[200], n, nm;
vector<cnt> b, p, e;
vector<long long> c;
vector<vector<long long> > q;
void modifu(int v, cnt x) {
  if (v == 0 || b[v].kl > x.kl) return;
  b[v] = x;
  modifu(v / 2, x);
}
cnt sn;
void find(int v, int l, int r, int l1, int r1) {
  if (l > r1 || r < l1) return;
  if (l >= l1 && r <= r1) {
    if (sn.kl < b[v].kl) sn = b[v];
    return;
  }
  find(v * 2, l, (l + r) / 2, l1, r1);
  find(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1);
}
void solv(int t) {
  for (int i(0); i < t; i++)
    for (int j(0); j < n; j++) c.push_back(a[j]);
  p.resize(c.size());
  b.resize(3 * nm);
  for (int i(0); i < c.size(); i++) {
    sn = cnt(0, 0);
    find(1, 1, nm, 1, c[i]);
    if (sn.kl == 0 && sn.pr == 0) sn.pr = -1;
    sn.kl++;
    p[i] = sn;
    sn.pr = i;
    modifu(nm + c[i] - 1, sn);
  }
}
bool check(int x, int y) {
  if (q[x].size() != q[y].size()) return false;
  for (int i(0); i < q[x].size(); i++)
    if (q[x][i] != q[y][i]) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  int t;
  cin >> n >> t;
  for (int i(0); i < n; i++) cin >> a[i];
  nm = 1;
  while (nm < 310) nm = nm * 2;
  if (t <= 400) {
    solv(t);
    long long ans = 0;
    for (int i(0); i < p.size(); i++)
      if (p[i].kl > ans) ans = p[i].kl;
    cout << ans;
    return 0;
  }
  solv(400);
  q.resize(500);
  long long v = 0, ns = 0;
  for (int i(0); i < p.size(); i++)
    if (p[i].kl > ns) {
      ns = p[i].kl;
      v = i;
    }
  while (v != -1) {
    int g = v / n;
    q[g].push_back(c[v]);
    v = p[v].pr;
  }
  long long ans = 0;
  ans = q[0].size();
  int j = 1;
  while (!check(j, j + 1)) {
    ans += q[j].size();
    j++;
  }
  int r = 399;
  ans += q[r].size();
  r--;
  int k = 1;
  while (!check(r, r + 1)) {
    ans += q[r].size();
    r--;
    k++;
  }
  long long kol = t - (k + j);
  ans = ans + kol * (q[j].size());
  cout << ans;
}

```