#include <bits/stdc++.h>
const int maxn = 1e5 + 7;
class TreeArray {
 private:
  int arr[maxn], n;
  int Lowbit(int x) { return x & (-x); }

 public:
  void Init(int x) {
    n = x;
    memset(arr, 0, sizeof(arr));
  }
  void AddVal(int pos, int val, int op) {
    if (op == 0) {
      while (pos) {
        arr[pos] = std ::max(arr[pos], val);
        pos -= Lowbit(pos);
      }
    } else {
      while (pos <= n) {
        arr[pos] = std ::max(arr[pos], val);
        pos += Lowbit(pos);
      }
    }
  }
  int Query(int pos, int op) {
    if (!pos) {
      return 0;
    }
    int res = 0;
    if (op == 0) {
      while (pos <= n) {
        res = std ::max(res, arr[pos]);
        pos += Lowbit(pos);
      }
    } else {
      while (pos) {
        res = std ::max(res, arr[pos]);
        pos -= Lowbit(pos);
      }
    }
    return res;
  }
};
class Solution {
 private:
  int n, t, a[maxn], start[maxn], end[maxn], maxx, sum[maxn];
  TreeArray tree;
  char res[maxn];
  long long ans, tot;

 public:
  Solution() {
    Get();
    Solve();
  }
  void Get() {
    scanf("%d %d", &n, &t);
    for (register int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      sum[a[i]]++;
      maxx = std ::max(maxx, a[i]);
      for (register int j = 1; j < std ::min(n, t); j++) {
        a[j * n + i] = a[i];
      }
    }
  }
  void Solve() {
    tree.Init(maxx);
    for (register int i = 1; i <= n * std ::min(n, t); i++) {
      end[i] = tree.Query(a[i], 1) + 1;
      ans = std ::max(ans, (long long)end[i]);
      tree.AddVal(a[i], end[i], 1);
    }
    if (t <= n) {
      printf("%lld\n", ans);
      return;
    }
    for (register int i = n * (n - 1) + 1; i <= n * n; i++) {
      tot = std ::max(tot, (long long)sum[a[i]] * (t - n));
    }
    printf("%lld\n", ans + tot);
  }
};
Solution sol;
int main() {}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
const int maxn = 1e5 + 7;
class TreeArray {
 private:
  int arr[maxn], n;
  int Lowbit(int x) { return x & (-x); }

 public:
  void Init(int x) {
    n = x;
    memset(arr, 0, sizeof(arr));
  }
  void AddVal(int pos, int val, int op) {
    if (op == 0) {
      while (pos) {
        arr[pos] = std ::max(arr[pos], val);
        pos -= Lowbit(pos);
      }
    } else {
      while (pos <= n) {
        arr[pos] = std ::max(arr[pos], val);
        pos += Lowbit(pos);
      }
    }
  }
  int Query(int pos, int op) {
    if (!pos) {
      return 0;
    }
    int res = 0;
    if (op == 0) {
      while (pos <= n) {
        res = std ::max(res, arr[pos]);
        pos += Lowbit(pos);
      }
    } else {
      while (pos) {
        res = std ::max(res, arr[pos]);
        pos -= Lowbit(pos);
      }
    }
    return res;
  }
};
class Solution {
 private:
  int n, t, a[maxn], start[maxn], end[maxn], maxx, sum[maxn];
  TreeArray tree;
  char res[maxn];
  long long ans, tot;

 public:
  Solution() {
    Get();
    Solve();
  }
  void Get() {
    scanf("%d %d", &n, &t);
    for (register int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      sum[a[i]]++;
      maxx = std ::max(maxx, a[i]);
      for (register int j = 1; j < std ::min(n, t); j++) {
        a[j * n + i] = a[i];
      }
    }
  }
  void Solve() {
    tree.Init(maxx);
    for (register int i = 1; i <= n * std ::min(n, t); i++) {
      end[i] = tree.Query(a[i], 1) + 1;
      ans = std ::max(ans, (long long)end[i]);
      tree.AddVal(a[i], end[i], 1);
    }
    if (t <= n) {
      printf("%lld\n", ans);
      return;
    }
    for (register int i = n * (n - 1) + 1; i <= n * n; i++) {
      tot = std ::max(tot, (long long)sum[a[i]] * (t - n));
    }
    printf("%lld\n", ans + tot);
  }
};
Solution sol;
int main() {}

```