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.

Difficulty: HARD
Tags: Matrices

Dynamic programming

Constructive algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(1):
	(n, m) = map(int, input().split())
	arr = list(list(map(int, input().split())))
	if m > 2 * n:
		dp = [0] * 303
		dp1 = [0] * 303
		d = {}
		for i in range(n):
			d[arr[i]] = d.get(arr[i], 0) + 1
			for j in range(n):
				dp[arr[j]] = max(dp[arr[j]] + 1, max(dp[:arr[j]]) + 1)
		for i in range(n):
			for j in range(n - 1, -1, -1):
				dp1[arr[j]] = max(dp1[arr[j]] + 1, max(dp1[arr[j] + 1:]) + 1)
		ans = 0
		for i in range(n):
			for j in range(n):
				if arr[j] < arr[i]:
					continue
				ans = max(ans, dp[arr[i]] + dp1[arr[j]] + (m - 2 * n) * d[arr[i]])
		print(ans)
	else:
		dp = [0] * 303
		for i in range(m):
			for j in range(n):
				dp[arr[j]] = max(dp[arr[j]] + 1, max(dp[:arr[j]]) + 1)
		print(max(dp))


from collections import Counter

def sub(seq):
	if not seq:
		return seq
	M = [None] * len(seq)
	P = [None] * len(seq)
	L = 1
	M[0] = 0
	for i in range(1, len(seq)):
		lower = 0
		upper = L
		if seq[M[upper - 1]] <= seq[i]:
			j = upper
		else:
			while upper - lower > 1:
				mid = (upper + lower) // 2
				if seq[M[mid - 1]] <= seq[i]:
					lower = mid
				else:
					upper = mid
			j = lower
		P[i] = M[j - 1]
		if j == L or seq[i] < seq[M[j]]:
			M[j] = i
			L = max(L, j + 1)
	result = []
	pos = M[L - 1]
	for _ in range(L):
		result.append(seq[pos])
		pos = P[pos]
	return result[::-1]
s = input('')
a = s.split(' ')
n = int(a[0])
t = int(a[1])
s = input('')
a = s.split(' ')
arr = []
for i in range(0, n):
	arr.append(int(a[i]))
m = min(t, n)
ar = []
for i in range(0, m):
	for j in range(0, n):
		ar.append(arr[j])
x = len(sub(ar))
m = t - m
data = Counter(arr)
c2 = data.most_common(1)
c = c2[0][1]
print(x + m * c)


mul = lambda A, B, r: [[max([A[i][k] + B[k][j] for k in r if A[i][k] and B[k][j]], default=0) for j in r] for i in r]

def binpower(A, n, e):
	r = range(n)
	B = A
	e -= 1
	while True:
		if e & 1:
			B = mul(B, A, r)
		e = e >> 1
		if e == 0:
			return B
		A = mul(A, A, r)

def f(l, n, T):
	h = max(l) + 1
	N = [[0] * h for _ in range(h)]
	Q = [[0] * h for _ in range(h)]
	M = [[0] * n for _ in range(n)]
	for j in range(n):
		for i in range(n):
			M[i][j] = Q[l[i]][l[j]] + 1 if l[i] <= l[j] else 0
		v = l[j]
		for u in range(1, v + 1):
			N[u][v] = Q[u][v] + 1
			for vv in range(v, h):
				Q[u][vv] = max(Q[u][vv], N[u][v])
	return max(max(binpower(M, n, T)))
(n, T) = list(map(int, input().split()))
l = list(map(int, input().split()))
print(f(l, n, T))


import sys
from collections import Counter
(n, t) = [int(i) for i in input().split()]
lst = [int(i) for i in input().split()]
cnt = Counter(lst)
mostlst = cnt.most_common()
freq = mostlst[0][1]
curlist = lst
curt = 1
d = [0 for i in range(n)]
prevmax = 0
curmax = 0
ans = 0
while curt <= t:
	d += [1 for i in range(n)]
	ind = curt * n
	for i in range(n):
		for j in range(-n, i):
			if lst[j] <= lst[i]:
				d[ind + i] = max(d[ind + i], d[ind + j] + 1)
	curmax = max(d[ind:ind + n])
	if curmax - prevmax == freq:
		ans = curmax + freq * (t - curt)
		break
	curt += 1
	prevmax = curmax
else:
	ans = curmax
print(ans)


import bisect
(n, T) = map(int, input().split())
As = list(map(int, input().split()))

def solve(n, T, As):
	if T <= 201:
		return len(LIS(As * T))
	lis = LIS(As * n)
	revAs = [-a for a in As[::-1]]
	lisrev = LIS(revAs * n)
	lisrev.sort()
	freq = [0] * 301
	for a in As:
		freq[a] += 1
	record = 0
	for (a, f) in enumerate(freq[1:], 1):
		if f == 0:
			continue
		head = bisect.bisect_right(lis, a)
		tail = bisect.bisect_right(lisrev, -a)
		length = head + tail + f * (T - 2 * n)
		if length > record:
			record = length
	return record

def LIS(As):
	L = [As[0]]
	for a in As[1:]:
		if a >= L[-1]:
			L.append(a)
		else:
			pos = bisect.bisect_right(L, a)
			L[pos] = a
	return L
print(solve(n, T, As))


def solve():
	(n, T) = map(int, input().split())
	array = list(map(int, input().split()))
	ElementsTillN = {}
	for x in range(n):
		ElementsTillN[x] = {array[x]: 1}
	for x in range(1, n):
		for y in range(x):
			if array[y] <= array[x]:
				for (value, num) in ElementsTillN[y].items():
					if value in ElementsTillN[x]:
						ElementsTillN[x][value] = max(num + 1, ElementsTillN[x][value])
					else:
						ElementsTillN[x][value] = num + 1
	newElementsTillN = {}
	for x in range(n):
		valueAtIndex = array[x]
		if valueAtIndex not in newElementsTillN:
			newElementsTillN[valueAtIndex] = {}
		for (value, num) in ElementsTillN[x].items():
			if value in newElementsTillN[valueAtIndex]:
				newElementsTillN[valueAtIndex][value] = max(num, newElementsTillN[valueAtIndex][value])
			else:
				newElementsTillN[valueAtIndex][value] = num
	valueSoFar = [0] * 301
	changes = [0] * 110
	for x in range(min(110, T)):
		currentSoFar = [0] * 301
		for end in newElementsTillN.keys():
			for start in array:
				if start <= end:
					for (newStart, value) in newElementsTillN[end].items():
						if newStart >= start:
							currentSoFar[end] = max(currentSoFar[end], value + valueSoFar[start])
		changes[x] = max(currentSoFar) - max(valueSoFar)
		valueSoFar = currentSoFar
	T -= 110
	if T > 0:
		print(max(valueSoFar) + T * changes[-1])
	else:
		print(max(valueSoFar))
solve()


import bisect

def LIS(As):
	L = [As[0]]
	for a in As[1:]:
		if a >= L[-1]:
			L.append(a)
		else:
			pos = bisect.bisect_right(L, a)
			L[pos] = a
	return L

def solve():
	(n, T) = map(int, input().split())
	array = list(map(int, input().split()))
	if T <= n + 1:
		print(len(LIS(array * T)))
	else:
		newarray = array * n
		lis = LIS(newarray)
		newlis = LIS(newarray + array)
		print(len(newlis) + (len(newlis) - len(lis)) * (T - n - 1))
solve()


f = lambda : map(int, input().split())
(n, m) = f()
t = list(f())
s = [0] * 301
d = s[:]
for i in t:
	d[i] += 1
for i in t * min(m, 2 * n):
	s[i] = max(s[:i + 1]) + 1
print(max(s) + max((m - n * 2) * max(d), 0))


f = lambda : map(int, input().split())
(n, m) = f()
t = list(f())
d = {i: j for (j, i) in enumerate(sorted(set(t)))}
t = [d[i] for i in t]
k = len(d)
a = [0] * k
if m < 2 * k:
	for j in t * m:
		a[j] += 1
		q = a[j]
		j += 1
		while j < k and a[j] < q:
			a[j] += 1
			j += 1
	print(a[-1])
	exit()
a = [0] * k
for j in t * k:
	a[j] += 1
	q = a[j]
	j += 1
	while j < k and a[j] < q:
		a[j] += 1
		j += 1
b = [0] * k
t.reverse()
for j in t * k:
	b[j] += 1
	q = b[j]
	j -= 1
	while j > -1 and b[j] < q:
		b[j] += 1
		j -= 1
print(max((a[j] + (m - 2 * k) * t.count(j) + b[j] for j in range(k))))