Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Once Again...

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an array of positive integers *a*_{1}, *a*_{2}, ..., *a*_{n × T} of length *n* × *T*. We know that for any *i* > *n* it is true that *a*_{i} = *a*_{i - 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 *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2021 06:44:57 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|