Codeforces Round #323 (Div. 2) D.Once Again... （nlogn LIS）

D. Once Again...

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 ≤ 10^7). 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.

题意是给出一个序列和k值，这个序列能循环k次，求其中的最长不下降子序列，k的值非常大，所以nlogn也要炸。仔细想一想，就算原数组中的所有数都进入了这个子序列中，也只有100个，剩下的肯定可以随意插入数字，那么这个数字显然是出现越多越好。那么就可以把原来的数组重复个许多(min(n, k))遍，求出其最长不下降子序列，在加上剩下的重复的序列中出现最多的数字的出现次数就是答案了。（其实我比赛时十多分钟就想到了，可惜发现以前居然把nlogn的LIS写挫了，我又抄了以前的orz）

#include<iostream>
#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 10;
int tt[110];
int num[maxn];
int dp[maxn];
map<int, int> mp;
int main() {
    int n, k;
    while(~scanf("%d %d", &n, &k)) {
        int maxnum = 0, maxcnt = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &tt[i]);
            mp[tt[i]]++;
            if(mp[tt[i]] > maxcnt) {
                maxnum = tt[i];
                maxcnt = mp[tt[i]];
            }
        }
        int cnt = 0;
        for(int i = 1; i <= min(n, k); i++) {
            for(int j = 1; j <= n; j++) {
                num[++cnt] = tt[j];
            }
        }
        int val = 0;
        //printf("%d
", cnt);
        for(int i = 1; i <= cnt; i++) {
            int pos = upper_bound(dp, dp + val, num[i]) - dp;
            if(pos == val) dp[val++] = num[i];
            else dp[pos] = num[i];
        }
        if(k > n) val = val + (k - n) * maxcnt;
        //cout << last << " " << maxcnt << endl;
        printf("%d
", val);
    }
}