#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> arr, arr2;
int dp[112][112][112];
map<int, int> myMap;
int mat[112][112], mat3[112][112];
void func() {
  for (int a = 0; a < 112; a++)
    for (int b = 0; b < 112; b++)
      for (int c = 0; c < 112; c++) dp[a][b][c] = 0;
  for (int a = 0; a <= myMap[arr[0]]; a++) dp[0][myMap[arr[0]]][a] = 1;
  int x;
  for (int a = 1; a < n; a++) {
    for (int b = 0; b < 112; b++)
      for (int c = 0; c < 112; c++) dp[a][b][c] = dp[a - 1][b][c];
    for (int c = 0; c <= myMap[arr[a]]; c++) {
      x = 0;
      for (int b = 0; b <= myMap[arr[a]]; b++) {
        x = max(x, dp[a - 1][b][c]);
      }
      dp[a][myMap[arr[a]]][c] = max(dp[a][myMap[arr[a]]][c], 1 + x);
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      mat[b][a] = dp[n - 1][a][b];
    }
  }
}
void mult(int Mat1[112][112], int Mat2[112][112]) {
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      mat3[a][b] = -9999999;
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      for (int c = 0; c < 112; c++) {
        mat3[a][b] = max(mat3[a][b], Mat1[a][c] + Mat2[c][b]);
      }
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      if (a > b) {
        mat3[a][b] = -9999999;
      }
      Mat1[a][b] = mat3[a][b];
    }
  }
}
void myPower(int Mat[112][112], int p) {
  if (p == 0 || p == 1) return;
  myPower(Mat, p / 2);
  mult(Mat, Mat);
  if (p % 2) mult(Mat, mat);
}
int main() {
  int t = 1, tt;
  while (t--) {
    int x;
    cin >> n >> tt;
    for (int a = 0; a < n; a++) {
      cin >> x;
      arr.push_back(x);
      arr2.push_back(x);
    }
    arr2.push_back(0);
    sort(arr2.begin(), arr2.end());
    unique(arr2.begin(), arr2.end());
    for (int a = 0; a < arr2.size(); a++) {
      myMap[arr2[a]] = a;
    }
    func();
    int myMat[112][112];
    for (int a = 0; a < 112; a++) {
      for (int b = 0; b < 112; b++) {
        if (mat[a][b] == 0) {
          mat[a][b] = -9999999;
        }
        myMat[a][b] = mat[a][b];
      }
    }
    myPower(myMat, tt);
    int ans = 1;
    for (int a = 0; a < 112; a++) {
      ans = max(ans, myMat[0][a]);
    }
    cout << ans << '\n';
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
using namespace std;
int n;
vector<int> arr, arr2;
int dp[112][112][112];
map<int, int> myMap;
int mat[112][112], mat3[112][112];
void func() {
  for (int a = 0; a < 112; a++)
    for (int b = 0; b < 112; b++)
      for (int c = 0; c < 112; c++) dp[a][b][c] = 0;
  for (int a = 0; a <= myMap[arr[0]]; a++) dp[0][myMap[arr[0]]][a] = 1;
  int x;
  for (int a = 1; a < n; a++) {
    for (int b = 0; b < 112; b++)
      for (int c = 0; c < 112; c++) dp[a][b][c] = dp[a - 1][b][c];
    for (int c = 0; c <= myMap[arr[a]]; c++) {
      x = 0;
      for (int b = 0; b <= myMap[arr[a]]; b++) {
        x = max(x, dp[a - 1][b][c]);
      }
      dp[a][myMap[arr[a]]][c] = max(dp[a][myMap[arr[a]]][c], 1 + x);
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      mat[b][a] = dp[n - 1][a][b];
    }
  }
}
void mult(int Mat1[112][112], int Mat2[112][112]) {
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      mat3[a][b] = -9999999;
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      for (int c = 0; c < 112; c++) {
        mat3[a][b] = max(mat3[a][b], Mat1[a][c] + Mat2[c][b]);
      }
    }
  }
  for (int a = 0; a < 112; a++) {
    for (int b = 0; b < 112; b++) {
      if (a > b) {
        mat3[a][b] = -9999999;
      }
      Mat1[a][b] = mat3[a][b];
    }
  }
}
void myPower(int Mat[112][112], int p) {
  if (p == 0 || p == 1) return;
  myPower(Mat, p / 2);
  mult(Mat, Mat);
  if (p % 2) mult(Mat, mat);
}
int main() {
  int t = 1, tt;
  while (t--) {
    int x;
    cin >> n >> tt;
    for (int a = 0; a < n; a++) {
      cin >> x;
      arr.push_back(x);
      arr2.push_back(x);
    }
    arr2.push_back(0);
    sort(arr2.begin(), arr2.end());
    unique(arr2.begin(), arr2.end());
    for (int a = 0; a < arr2.size(); a++) {
      myMap[arr2[a]] = a;
    }
    func();
    int myMat[112][112];
    for (int a = 0; a < 112; a++) {
      for (int b = 0; b < 112; b++) {
        if (mat[a][b] == 0) {
          mat[a][b] = -9999999;
        }
        myMat[a][b] = mat[a][b];
      }
    }
    myPower(myMat, tt);
    int ans = 1;
    for (int a = 0; a < 112; a++) {
      ans = max(ans, myMat[0][a]);
    }
    cout << ans << '\n';
  }
  return 0;
}

```