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. 
import java.util.*;
import java.io.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,t;
        int ans = -1;
        n = scan.nextInt();
        t = scan.nextInt();
        int arr[] = new int[n+1];
        int cnt[] = new int[300+1];
        for(int i = 0 ; i <= 300 ; i++) cnt[i] = 0;
        for(int i = 0 ; i < n ; i++){
            arr[i] = scan.nextInt();
            cnt[arr[i]]++;
        }
        if(t <= 200){
            int tmp[] = new int[t*n+1];
            for(int i = 0 ; i < t ; i++){
                for(int j = 0 ;  j < n ; j++){
                    tmp[i*n + j] = arr[j];
                }
            }
            //int[] dp = dpl(tmp,t*n);
            int[] dp = dpr(tmp,t*n);
            for(int i = 0 ; i < t*n ; i++){
                //System.out.print(dp[i] + " ");
                ans = Math.max(ans, dp[i]);
            }
            //System.out.print("\n");
        }
        else{
            int tmp[] = new int[100*n+1];
            for(int i = 0 ; i < 100 ; i++){
                for(int j = 0 ;  j < n ; j++){
                    tmp[i*n + j] = arr[j];
                }
            }
            int[] ldp = dpl(tmp,100*n);
            int[] rdp = dpr(tmp,100*n);
            int[] getl = new int[300+1];
            int[] getr = new int[300+1];
            
            for(int i = 0 ; i < n ; i++){
                int _max = -1;
                int _min = 101;
                for(int j = 0 ; j < n ; j++){
                    if(arr[j] == arr[i]){
                        _max = Math.max(_max, j);
                        _min = Math.min(_min, j);
                    }
                }
                getl[arr[i]] = _min;
                getr[arr[i]] = _max;
            }
            boolean visited[] = new boolean[301];
            for(int i = 0 ; i <= 300 ; i++) visited[i] = false;
            for(int i = 0 ; i < n ; i++){
                if(!visited[arr[i]]){
                    int l = ldp[99*n+getr[arr[i]]];
                    int mid = (t-200) * cnt[arr[i]];
                    int r = rdp[getl[arr[i]]];
                    ans = Math.max(ans, l+mid+r);
                }
            }
            
        }
        System.out.println(ans);  
    }
    
    public static int[] dpl(int[] arr, int n){
        int ans[] = new int[n+1];
        int dp[] = new int[n+2];
        dp[0] = -1; dp[1] = arr[0];
        ans[0] = 1;
        int len = 1;
        for(int i = 1 ; i < n ; i++){
            int l = search(dp,len,arr[i]);
            dp[l] = arr[i];
            ans[i] = l;
            len = Math.max(len, l);
        }
        return ans;
    }
    
    public static int[] dpr(int[] arr, int n){
        int ans[] = new int[n+1];
        int dp[] = new int[n+2];
        dp[0] = -1; dp[1] = arr[n-1];
        ans[n-1] = 1;
        int len = 1;
        for(int i = n-2 ; 0 <= i ; i--){
            int l = search2(dp,len,arr[i]);
            dp[l] = arr[i];
            ans[i] = l;
            len = Math.max(len, ans[i]);
        }
        return ans;
    }
    
    public static int search2(int arr[], int len,int num){
        //System.out.println("num = " + num);
        int l = 1;int r = len;
        while(l <= r){
            //System.out.println("l = " + l + " r = " + r);
            int mid = (l+r)/2;
            if(arr[mid] >= num) l = mid+1;
            else r = mid - 1;
        }
        return l;
    }
    
    public static int search(int arr[], int len, int num){
        //System.out.println("num = " + num);
        int l = 1;int r = len;
        while(l <= r){
            //System.out.println("l = " + l + " r = " + r);
            int mid = (l+r)/2;
            if(num < arr[mid]) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
    
}


