Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an integer $K$ and a random permutation ― sequence $A_{1}, A_{2}, \ldots, A_{N}$ of integers $1$ through $N$. You have to perform the following process:
1. Split the permutation $A$ into $K$ non-empty contiguous subsequences $S_{1}, S_{2}, \dots, S_{K}$ such that each element of $A$ appears in exactly one of them.
2. Choose an arbitrary permutation $P$ of the integers $1$ through $K$.
3. Create a new permutation $B_{1}, B_{2}, \ldots, B_{N}$ by concatenating the sequences $S_{P_{1}}, S_{P_{2}}, \ldots, S_{P_{K}}$ in this order.

You are allowed to split the permutation $A$ into $K$ subsequences in any valid way and choose any permutation $P$ you want. Your goal is to make the length of the longest increasing subsequence of the permutation $B$ as large as possible.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
Print a single line containing $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.

------  Constraints ------
$5 ≤ N ≤ 5 \cdot 10^{5}$
$3 ≤ K ≤ N$
$1 ≤ A_{i} ≤ N$ for each valid $i$
$A_{i} \neq A_{j}$ for each valid $i, j$ ($i \neq j$)

------  Scoring ------
In each test case (and therefore each test file), let $L_{A}$ and $L_{B}$ be the lengths of the longest increasing subsequences of the permutations $A$ and $B$ respectively. If $L_{B} ≤ L_{A}$, your submission will receive the Wrong Answer verdict. Otherwise, your score for this test case is $(L_{B} - L_{A}) \cdot W$, where $W$ is a parameter of the grader. The values of $W$ for all tests are specified in the Test Generation section. The score of a submission is equal to the sum of its scores over all test cases. The goal is to maximise the score of your submission.

There are 18 test files. During the contest, the displayed score will account for exactly five test files (belonging to groups 1, 3, 5, 7, 9 from the test generation section), i.e. your score reflects your submission's performance on roughly 28% (5 / 18) of the test files. However, if your program gets a non-AC verdict on any test file, your submission's verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other $13$ test files.

------  Example Input ------

7 3
5 3 7 1 2 6 4

------  Example Output ------

1 2 6 4 5 3 7

------  Explanation ------
The permutation $B = (1, 2, 6, 4, 5, 3, 7)$ could be obtained from $A = (5, 3, 7, 1, 2, 6, 4)$ in the following way:
1. Choose subsequences $S_{1} = (5, 3)$, $S_{2} = (7)$, $S_{3} = (1, 2, 6, 4)$.
2. Choose the permutation $P = (3, 1, 2)$.
3. Concatenate $S_{P_{1}}, S_{P_{2}}, S_{P_{3}} = S_{3}, S_{1}, S_{2} = (1, 2, 6, 4), (5, 3), (7)$.

The longest increasing subsequence of $A$ is $(1, 2, 6)$ and its length is $L_{A} = 3$. The longest increasing subsequence of $B$ is $(1, 2, 4, 5, 7)$ and its length is $L_{B} = 5$. If $W = 1$, the final score of this solution on this test case is $L_{B} - L_{A} = 5 - 3 = 2$.

------  Test generation ------
There are nine test groups. In each test group, there are two test cases; the values of $N$, $K$ and $W$ (the scoring coefficient) are listed in the table below. In each test case, the permutation $A$ is chosen uniformly randomly among all $N!-1$ permutations other than $1, 2, \ldots, N-1, N$.

Group
N
K
W
    
1
5 · 10^{3}
50
8284
    
2
5 · 10^{3}
140
4745
    
3
5 · 10^{3}
400
2124
    
4
5 · 10^{4}
150
2676
    
5
5 · 10^{4}
450
1484
    
6
5 · 10^{4}
1500
580
    
7
5 · 10^{5}
500
828
    
8
5 · 10^{5}
1400
474
    
9
5 · 10^{5}
5000
175

Difficulty: VERY_HARD

Starter code:

Solutions:
from bisect import bisect
(n, k) = map(int, input().split())
K = k
data = list(map(int, input().split()))
inlis = [0] * n

def upperbound(data, T, key, l, r):
	while r - l > 1:
		m = l + (r - l) // 2
		if data[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def ubound(tails, data, l, r, s):
	if s >= data[tails[r]]:
		return r + 1
	elif s < data[tails[l]]:
		return 0
	if r - l < 2:
		return r
	mid = (l + r) // 2
	if data[tails[mid]] <= s:
		ans = ubound(tails, data, mid, r, s)
	else:
		ans = ubound(tails, data, l, mid, s)
	return ans

def lislen(data, x=0, y=10 ** 9):
	data = [i for i in data if x <= i <= y]
	tails = [0 for i in range(len(data))]
	index = 1
	for i in range(1, len(data)):
		if data[i] < data[tails[0]]:
			tails[0] = i
		elif data[i] > data[tails[index - 1]]:
			tails[index] = i
			index += 1
		else:
			pos = ubound(tails, data, 0, index - 1, data[i])
			tails[pos] = i
	return index

def lismark(data, inlis):
	tails = [0 for i in range(len(data))]
	prevs = [-1 for i in range(len(data))]
	index = 1
	for i in range(1, len(data)):
		if data[i] < data[tails[0]]:
			tails[0] = i
		elif data[i] >= data[tails[index - 1]]:
			prevs[i] = tails[index - 1]
			tails[index] = i
			index += 1
		else:
			pos = upperbound(data, tails, data[i], -1, index - 1)
			prevs[i] = tails[pos - 1]
			tails[pos] = i
	i = tails[index - 1]
	imax = i
	imin = 0
	while i >= 0:
		if data[i] < data[imin]:
			imin = i
		inlis[i] = 1
		i = prevs[i]
	return (index, imax, imin)
if n == k:
	print(*sorted(data))
else:
	(olis, imax, imin) = lismark(data, inlis)
	ans = []
	if olis != n:
		if k > 3 or imax != n - 1 or imin != 0:
			process = []
			used = [0] * n
			index = 0
			while k > 2 and index < imin:
				process.append(data[index])
				used[index] = 1
				index += 1
				k -= 2
			index = n - 1
			while k > 2 and index > imax:
				process.append(data[index])
				used[index] = 1
				index -= 1
				k -= 2
			index = 0
			while k > 3 and index < imax:
				if not inlis[index] and (not used[index]):
					process.append(data[index])
					used[index] = 1
					k -= 3
				index += 1
			process.sort()
			a = 0
			b = 0
			while a < len(process) and b < len(data):
				if used[b]:
					b += 1
					continue
				while a < len(process) and inlis[b] and (data[b] >= process[a]):
					ans.append(process[a])
					a += 1
				ans.append(data[b])
				b += 1
			while b < len(data):
				if used[b]:
					b += 1
					continue
				ans.append(data[b])
				b += 1
			while a < len(process):
				ans.append(process[a])
				a += 1
		else:
			index = 0
			segs = []
			mic = mac = 0
			for i in range(n):
				if inlis[i]:
					if index != i:
						segs.append((index, i - 1, mic, mac))
					index = i + 1
					mic = mac = 0
				else:
					if data[i] <= data[imin]:
						mic += 1
					if data[i] >= data[imax]:
						mac += 1
			gain = 0
			iseg = 0
			inStart = True
			for i in range(len(segs)):
				if segs[i][2] > gain:
					gain = segs[i][2]
					iseg = i
					inStart = True
				if segs[i][3] > gain:
					gain = segs[i][3]
					iseg = i
					inStart = False
			if inStart:
				ans.extend(data[segs[iseg][0]:segs[iseg][1] + 1])
			ans.extend(data[:segs[iseg][0]])
			ans.extend(data[segs[iseg][1] + 1:])
			if not inStart:
				ans.extend(data[segs[iseg][0]:segs[iseg][1] + 1])
	nlis = lislen(ans)
	ns1lis = K - 1 + lislen(data[K - 1:], max(data[:K - 1]))
	ns2lis = K - 1 + lislen(data[K - 1:], y=min(data[:K - 1]))
	ne1lis = K - 1 + lislen(data[:-K + 1], max(data[-K + 1:]))
	ne2lis = K - 1 + lislen(data[:-K + 1], y=min(data[-K + 1:]))
	if nlis < ns1lis:
		nlis = ns1lis
		ans = sorted(data[:K - 1]) + data[K - 1:]
	if nlis < ns2lis:
		nlis = ns2lis
		ans = data[K - 1:] + sorted(data[:K - 1])
	if nlis < ne1lis:
		nlis = ne1lis
		ans = sorted(data[-K + 1:]) + data[:-K + 1]
	if nlis < ne2lis:
		nlis = ne2lis
		ans = data[:-K + 1] + sorted(data[-K + 1:])
	if n < 5500:
		sdata = sorted(data)
		k = K
		used = [0] * n
		i = j = 0
		while k > 2:
			for x in range(n):
				if not used[x] and data[x] == sdata[j]:
					used[x] = 1
					j += 1
					i = x + 1
					break
			while i < n and j < n and (data[i] == sdata[j]) and (not used[i]):
				used[i] = 1
				i += 1
				j += 1
			k -= 2
		d1 = sdata[:j] + [data[i] for i in range(n) if not used[i]]
		d1lis = lislen(d1)
		if nlis < d1lis:
			nlis = d1lis
			ans = d1
		k = K
		used = [0] * n
		i = j = n - 1
		while k > 2:
			for x in range(n):
				if not used[x] and data[x] == sdata[j]:
					used[x] = 1
					j -= 1
					i = x - 1
					break
			while i >= 0 and j >= 0 and (data[i] == sdata[j]) and (not used[i]):
				used[i] = 1
				i -= 1
				j -= 1
			k -= 2
		d2 = [data[i] for i in range(n) if not used[i]] + sdata[j + 1:]
		d2lis = lislen(d2)
		if nlis < d2lis:
			nlis = d2lis
			ans = d2
	print(*ans)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
for i in range(1, k - k // 2):
	print(i, end=' ')
for i in range(n):
	if l[i] >= k - k // 2:
		print(l[i], end=' ')


def search(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A):
	size = len(A)
	tailTable = [0 for i in range(size + 1)]
	tailTable[0] = A[0]
	_len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[_len - 1]:
			tailTable[_len] = A[i]
			_len += 1
		else:
			tailTable[search(tailTable, -1, _len - 1, A[i])] = A[i]
	return _len
(N, K) = map(int, input().split())
arr = list(map(int, input().split()))
cnt = (K - 1) // 2
ansmin = []
for i in range(1, cnt + 1):
	ansmin.append(i)
for i in arr:
	if i > cnt:
		ansmin.append(i)
cnt = N - cnt + 1
ansmax = []
for i in arr:
	if i < cnt:
		ansmax.append(i)
for i in range(cnt, N + 1):
	ansmax.append(i)
_lansmin = LIS(ansmin)
_lansmax = LIS(ansmax)
if _lansmin > _lansmax:
	print(*ansmin)
else:
	print(*ansmax)


(N, K) = map(int, input().split())
lst = list(map(int, input().split()))
mx = max(lst)
for i in range(N):
	if lst[i] == mx:
		lst = lst[:i] + lst[i + 1:] + [mx]
		break
if K > 5:
	mn = min(lst)
	for i in range(N):
		if lst[i] == mn:
			lst = [mn] + lst[:i] + lst[i + 1:]
			break
if N == K:
	lst.sort()
K -= 3
if K > 2:
	arr = lst[:K - 1]
	arr.sort()
	lst = arr + lst[K - 1:]
print(*lst)


import sys

def input():
	return sys.stdin.readline().strip()

def array_lele():
	return list(map(int, sys.stdin.readline().strip().split()))

def integers_lele():
	return map(int, sys.stdin.readline().strip().split())

def CeilIndex(v, l, r, key):
	while r - l > 1:
		m = (l + r) // 2
		if v[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(v):
	if len(v) == 0:
		return 0
	tail = [0] * len(v)
	length = 1
	tail[0] = v[0]
	for i in range(1, len(v)):
		if v[i] < tail[0]:
			tail[0] = v[i]
		elif v[i] > tail[length - 1]:
			tail[length] = v[i]
			length += 1
		else:
			tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i]
	return length
(N, K) = integers_lele()
Arr = array_lele()
Arr2 = reversed(Arr)
if N == K:
	result = sorted(Arr)
	print(*result)
	exit()
result = []
i = 0
count = 0
while i < N and count < K:
	j = i
	new = []
	new.append(Arr[j])
	j = j + 1
	while j < N and Arr[j] > Arr[j - 1]:
		new.append(Arr[j])
		j = j + 1
	i = j
	count = count + 1
	result.append(new)
while i < N:
	result[-1].append(Arr[i])
	i = i + 1
answer1 = result.copy()
answer1.sort()
normal = []
answer2 = result.copy()
answer2.sort(key=lambda z: z[-1])
ordinary = []
for i in answer1:
	for j in i:
		normal.append(j)
for i in answer2:
	for j in i:
		ordinary.append(j)
lis1 = LIS(normal)
lis2 = LIS(ordinary)
maxi = 0
if lis1 > lis2:
	maxi = lis1
	answer = normal
else:
	maxi = lis2
	answer = ordinary
result = []
i = 0
count = 0
while i < N and count < K:
	j = i
	new = []
	new.append(Arr[j])
	j = j + 1
	while j < N and Arr[j] < Arr[j - 1]:
		new.append(Arr[j])
		j = j + 1
	i = j
	count = count + 1
	result.append(new)
while i < N:
	result[-1].append(Arr[i])
	i = i + 1
answer1 = result.copy()
answer1.sort()
normal = []
answer2 = result.copy()
answer2.sort(key=lambda z: z[-1])
ordinary = []
for i in answer1:
	for j in i:
		normal.append(j)
for i in answer2:
	for j in i:
		ordinary.append(j)
lis1 = LIS(normal)
lis2 = LIS(ordinary)
if lis1 > lis2:
	second = lis1
	answer10 = normal
else:
	second = lis2
	answer10 = ordinary
if maxi > second:
	print(*answer)
else:
	print(*answer10)


def ceilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def LIS(arr, n):
	tail = [0 for i in range(n + 1)]
	prev = [-1 for i in range(n + 1)]
	len = 1
	for i in range(1, n):
		if arr[i] < arr[tail[0]]:
			tail[0] = i
		elif arr[i] > arr[tail[len - 1]]:
			prev[i] = tail[len - 1]
			tail[len] = i
			len += 1
		else:
			pos = ceilIndex(arr, tail, -1, len - 1, arr[i])
			prev[i] = tail[pos - 1]
			tail[pos] = i
	return len
from random import shuffle
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
LA = LIS(a, n)
LB = LA
ans = []
poss_points = list(range(1, n - 1))
place = list(range(k))
while LB <= LA:
	shuffle(poss_points)
	points = [0] + sorted(poss_points[:k - 1]) + [n]
	shuffle(place)
	ans = []
	for i in range(k):
		part_index = place[i]
		ans.extend(a[points[part_index]:points[part_index + 1]])
	LB = LIS(ans, n)
print(*ans)


def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	if size == 1:
		return 1
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
(N, K) = map(int, input().split())
A = input().split()
for i in range(N):
	A[i] = int(A[i])
B = []
C = []
for i in range(N):
	if i == 0:
		C.append(A[i])
		if i == N - 1:
			B.append(C)
	elif A[i] - A[i - 1] == 1:
		C.append(A[i])
		if i == N - 1:
			B.append(C)
	else:
		B.append(C)
		C = [A[i]]
		if i == N - 1:
			B.append(C)
if len(B) <= K:
	for i in range(N):
		print(i + 1, end=' ')
else:
	count1 = 0
	for i in range((K - 1) // 2):
		if A[i] == i + 1:
			count1 += 1
	count2 = 0
	for i in range((K - 1) // 2):
		if A[N - i - 1] == N - i:
			count2 += 1
	D = [i + 1 for i in range((K - 1) // 2 + count1)]
	last = D[len(D) - 1]
	for i in range(N):
		if A[i] > last:
			D.append(A[i])
	E = [N - i for i in range((K - 1) // 2 + count2)]
	last = E[len(E) - 1]
	for i in range(N):
		if A[N - i - 1] < last:
			E.append(A[N - i - 1])
	F = []
	for i in range(N):
		F.append(E[N - 1 - i])
	if LongestIncreasingSubsequenceLength(D, N) >= LongestIncreasingSubsequenceLength(F, N):
		print(*D)
	else:
		print(*F)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
max_index = A.index(N)
i = 0
while K >= 3:
	max_index = A.index(N - i)
	(A[max_index], A[N - i - 1]) = (A[N - i - 1], A[max_index])
	K -= 4
for i in A:
	print(i, end=' ')
print()


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(1, k // 3 + 1):
	print(i, end=' ')
for i in a:
	if i > k // 3:
		print(i, end=' ')


from bisect import bisect, insort_left
(n, k) = map(int, input().split())
K = k
data = list(map(int, input().split()))
inlis = [0] * n

def upperbound(data, T, key, l, r):
	while r - l > 1:
		m = l + (r - l) // 2
		if data[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def ubound(tails, data, l, r, s):
	if s >= data[tails[r]]:
		return r + 1
	elif s < data[tails[l]]:
		return 0
	if r - l < 2:
		return r
	mid = (l + r) // 2
	if data[tails[mid]] <= s:
		ans = ubound(tails, data, mid, r, s)
	else:
		ans = ubound(tails, data, l, mid, s)
	return ans

def lislen(data, x=0, y=10 ** 9):
	data = [i for i in data if x <= i <= y]
	tails = [0 for i in range(len(data))]
	index = 1
	for i in range(1, len(data)):
		if data[i] < data[tails[0]]:
			tails[0] = i
		elif data[i] > data[tails[index - 1]]:
			tails[index] = i
			index += 1
		else:
			pos = ubound(tails, data, 0, index - 1, data[i])
			tails[pos] = i
	return index

def lismark(data, inlis):
	tails = [0 for i in range(len(data))]
	prevs = [-1 for i in range(len(data))]
	index = 1
	for i in range(1, len(data)):
		if data[i] < data[tails[0]]:
			tails[0] = i
		elif data[i] >= data[tails[index - 1]]:
			prevs[i] = tails[index - 1]
			tails[index] = i
			index += 1
		else:
			pos = upperbound(data, tails, data[i], -1, index - 1)
			prevs[i] = tails[pos - 1]
			tails[pos] = i
	i = tails[index - 1]
	imax = i
	imin = 0
	while i >= 0:
		if data[i] < data[imin]:
			imin = i
		inlis[i] = 1
		i = prevs[i]
	return (index, imax, imin)
if n == k:
	print(*sorted(data))
else:
	(olis, imax, imin) = lismark(data, inlis)
	ans = []
	if olis != n:
		if k > 3 or imax != n - 1 or imin != 0:
			process = []
			used = [0] * n
			index = 0
			while k > 2 and index < imin:
				process.append(data[index])
				used[index] = 1
				index += 1
				k -= 2
			index = n - 1
			while k > 2 and index > imax:
				process.append(data[index])
				used[index] = 1
				index -= 1
				k -= 2
			index = 0
			while k > 3 and index < imax:
				if not inlis[index] and (not used[index]):
					process.append(data[index])
					used[index] = 1
					k -= 3
				index += 1
			process.sort()
			a = 0
			b = 0
			while a < len(process) and b < len(data):
				if used[b]:
					b += 1
					continue
				while a < len(process) and inlis[b] and (data[b] >= process[a]):
					ans.append(process[a])
					a += 1
				ans.append(data[b])
				b += 1
			while b < len(data):
				if used[b]:
					b += 1
					continue
				ans.append(data[b])
				b += 1
			while a < len(process):
				ans.append(process[a])
				a += 1
		else:
			index = 0
			segs = []
			mic = mac = 0
			for i in range(n):
				if inlis[i]:
					if index != i:
						segs.append((index, i - 1, mic, mac))
					index = i + 1
					mic = mac = 0
				else:
					if data[i] <= data[imin]:
						mic += 1
					if data[i] >= data[imax]:
						mac += 1
			gain = 0
			iseg = 0
			inStart = True
			for i in range(len(segs)):
				if segs[i][2] > gain:
					gain = segs[i][2]
					iseg = i
					inStart = True
				if segs[i][3] > gain:
					gain = segs[i][3]
					iseg = i
					inStart = False
			if inStart:
				ans.extend(data[segs[iseg][0]:segs[iseg][1] + 1])
			ans.extend(data[:segs[iseg][0]])
			ans.extend(data[segs[iseg][1] + 1:])
			if not inStart:
				ans.extend(data[segs[iseg][0]:segs[iseg][1] + 1])
	nlis = lislen(ans)
	ns1lis = K - 1 + lislen(data[K - 1:], max(data[:K - 1]))
	ns2lis = K - 1 + lislen(data[K - 1:], y=min(data[:K - 1]))
	ne1lis = K - 1 + lislen(data[:-K + 1], max(data[-K + 1:]))
	ne2lis = K - 1 + lislen(data[:-K + 1], y=min(data[-K + 1:]))
	if nlis < ns1lis:
		nlis = ns1lis
		ans = sorted(data[:K - 1]) + data[K - 1:]
	if nlis < ns2lis:
		nlis = ns2lis
		ans = data[K - 1:] + sorted(data[:K - 1])
	if nlis < ne1lis:
		nlis = ne1lis
		ans = sorted(data[-K + 1:]) + data[:-K + 1]
	if nlis < ne2lis:
		nlis = ne2lis
		ans = data[:-K + 1] + sorted(data[-K + 1:])
	used = [0] * n
	(i, j) = (0, n - 1)
	add = []
	k = K
	while k > 1 and i < n and (j >= 0):
		if used[i]:
			i += 1
			continue
		if used[j]:
			j -= 1
			continue
		if data[i] <= data[j]:
			add.append(data[i])
			used[i] = 1
			i += 1
		else:
			add.append(data[j])
			used[j] = 1
			j -= 1
		k -= 1
	mi1 = sorted(add) + [data[i] for i in range(n) if not used[i]]
	mi2 = [data[i] for i in range(n) if not used[i]] + sorted(add)
	mi1lis = lislen(mi1)
	mi2lis = lislen(mi2)
	if nlis < mi1lis:
		nlis = mi1lis
		ans = mi1
	if nlis < mi2lis:
		nlis = mi2lis
		ans = mi2
	used = [0] * n
	(i, j) = (0, n - 1)
	add = []
	k = K
	while k > 1 and i < n and (j >= 0):
		if used[i]:
			i += 1
			continue
		if used[j]:
			j -= 1
			continue
		if data[i] >= data[j]:
			add.append(data[i])
			used[i] = 1
			i += 1
		else:
			add.append(data[j])
			used[j] = 1
			j -= 1
		k -= 1
	ma1 = [data[i] for i in range(n) if not used[i]] + sorted(add)
	ma2 = sorted(add) + [data[i] for i in range(n) if not used[i]]
	ma1lis = lislen(ma1)
	ma2lis = lislen(ma2)
	if nlis < ma1lis:
		nlis = ma1lis
		ans = ma1
	if nlis < ma2lis:
		nlis = ma2lis
		ans = ma2
	if n <= 5000:
		sdata = sorted(data)
		k = K
		used = [0] * n
		i = j = 0
		while k > 2:
			for x in range(n):
				if not used[x] and data[x] == sdata[j]:
					used[x] = 1
					j += 1
					i = x + 1
					break
			while i < n and j < n and (data[i] == sdata[j]) and (not used[i]):
				used[i] = 1
				i += 1
				j += 1
			k -= 2
		d1 = sdata[:j] + [data[i] for i in range(n) if not used[i]]
		d1lis = lislen(d1)
		if nlis < d1lis:
			nlis = d1lis
			ans = d1
		k = K
		used = [0] * n
		i = j = n - 1
		while k > 2:
			for x in range(n):
				if not used[x] and data[x] == sdata[j]:
					used[x] = 1
					j -= 1
					i = x - 1
					break
			while i >= 0 and j >= 0 and (data[i] == sdata[j]) and (not used[i]):
				used[i] = 1
				i -= 1
				j -= 1
			k -= 2
		d2 = [data[i] for i in range(n) if not used[i]] + sdata[j + 1:]
		d2lis = lislen(d2)
		if nlis < d2lis:
			nlis = d2lis
			ans = d2
		k = K
		s = K - 1
		for i in range(1, len(data) - s, 100):
			d1 = data[:i]
			d2 = data[i:i + s]
			d3 = data[i + s:]
			sd2 = sorted(d2)
			p1 = sd2 + d1 + d3
			p2 = sd2 + d3 + d1
			p3 = d1 + d3 + sd2
			p4 = d3 + d1 + sd2
			p1lis = lislen(p1)
			p2lis = lislen(p2)
			p3lis = lislen(p3)
			p4lis = lislen(p4)
			if p1lis > nlis:
				ans = p1
			if p2lis > nlis:
				ans = p2
			if p3lis > nlis:
				ans = p3
			if p4lis > nlis:
				ans = p4
	print(*ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
max_index = A.index(N)
if max_index != N - 1:
	(A[N - 1], A[max_index]) = (A[max_index], A[N - 1])
	K -= 5
if K > 0:
	(A[A.index(1)], A[0]) = (A[0], 1)
for i in A:
	print(i, end=' ')
print()


import sys

def IN(f=0):
	if f == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
(n, k) = IN()
a = IN()
if max(a) != a[-1]:
	j = a.index(max(a))
	b = a[:j] + a[j + 1:] + [a[j]]
	print(*b)
elif min(a) != a[0]:
	j = a.index(min(a))
	b = [a[j]] + a[:j] + a[j + 1:]
	print(*b)


import collections
from bisect import bisect_left

def BinarySearch(l, x):
	i = bisect_left(l, x)
	if i:
		return i - 1
	else:
		return -1

def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A, size):
	if size == 0:
		return 1
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
(n, k) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split(' ')))
temparr = arr.copy()
marri = {}
for i in range(n):
	marri[arr[i]] = i
marr = sorted(arr)
arrm = sorted(arr, reverse=True)
ede = collections.deque([])
ode = collections.deque([])
anslist1 = []
anslist2 = []
ind2 = {}
d = {0: n - 1}
ind = {}
i = 0
j = 0
loop = 0
mi = -10
while k > len(d) + len(ind2) and i + j < n:
	flag = 1
	if loop % 2:
		prev = mi
		mi = marri[marr[i]]
		if mi - 1 == prev:
			ind2[prev] = mi
			ind[mi] = mi
			ode.append(arr[mi])
			i += 1
			continue
	else:
		prev = mi
		mi = marri[arrm[j]]
		if mi + 1 == prev:
			del ind2[prev]
			ind2[mi] = prev
			ind[mi] = mi
			ede.appendleft(arr[mi])
			j += 1
			continue
	if mi in d:
		ind[mi] = mi
		ind2[mi] = mi
		if mi + 1 == d[mi]:
			ind[mi + 1] = mi + 1
			ind2[mi + 1] = mi + 1
		else:
			d[mi + 1] = d[mi]
		del d[mi]
	elif mi in ind:
		pass
	else:
		l = list(sorted(d))
		x = BinarySearch(l, mi)
		if x != -1:
			y = d[l[x]]
			x = l[x]
		else:
			x = 0
			y = d[l[x]]
		if x < mi and y > mi:
			del d[x]
			if len(d) + len(ind2) < k - 2:
				if x == mi - 1:
					ind[x] = x
					ind2[x] = x
				else:
					d[x] = mi - 1
				if y == mi + 1:
					ind[y] = y
					ind2[y] = y
				else:
					d[mi + 1] = y
				ind[mi] = mi
				ind2[mi] = mi
			else:
				if x == mi - 1:
					ind[x] = x
				d[x] = mi - 1
				d[mi] = y
				flag = 0
		elif x == mi:
			del d[x]
			ind[x] = x
			ind2[x] = x
			if x + 1 == y:
				ind[y] = y
				ind2[y] = y
			else:
				d[x + 1] = y
		elif y == mi:
			ind[y] = y
			ind2[y] = y
			if x == y - 1:
				del d[x]
				ind[x] = x
				ind2[x] = x
			else:
				d[x] = y - 1
	if flag:
		if loop % 2:
			ode.append(arr[mi])
			i += 1
		else:
			ede.appendleft(arr[mi])
			j += 1
	loop += 1
vis = {}
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[min(ans)] = ans
for i in sorted(ode):
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in sorted(ede):
	vis[i] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
for i in sorted(ode):
	anslist2.append(i)
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
for i in sorted(ede):
	anslist2.append(i)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[max(ans)] = ans
vis = {}
for i in sorted(ode):
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in sorted(ede):
	vis[i] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
anslist2.clear()
for i in sorted(ode):
	anslist2.append(i)
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
for i in sorted(ede):
	anslist2.append(i)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
arr = temparr.copy()
marr = sorted(arr)
de = collections.deque([])
l = []
d = {0: n - 1}
ind = {}
ind2 = {}
i = 0
mi = -10
while k > len(d) + len(ind2):
	flag = 1
	prev = mi
	mi = marri[marr[i]]
	if mi - 1 == prev:
		ind2[prev] = mi
		ind[mi] = mi
		de.append(arr[mi])
		i += 1
		continue
	if mi in d:
		ind[mi] = mi
		ind2[mi] = mi
		if mi + 1 == d[mi]:
			ind[mi + 1] = mi + 1
			ind2[mi + 1] = mi + 1
		else:
			d[mi + 1] = d[mi]
		del d[mi]
	elif mi in ind:
		pass
	else:
		l = list(sorted(d))
		x = BinarySearch(l, mi)
		if x != -1:
			y = d[l[x]]
			x = l[x]
		else:
			x = 0
			y = d[l[x]]
		if x < mi and y > mi:
			del d[x]
			if len(d) + len(ind2) < k - 2:
				if x == mi - 1:
					ind[x] = x
					ind2[x] = x
				else:
					d[x] = mi - 1
				if y == mi + 1:
					ind[y] = y
					ind2[y] = y
				else:
					d[mi + 1] = y
				ind[mi] = mi
				ind2[mi] = mi
			else:
				if x == mi - 1:
					ind[x] = x
				d[x] = mi - 1
				d[mi] = y
				flag = 0
		elif x == mi:
			del d[x]
			ind[x] = x
			ind2[x] = x
			if x + 1 == y:
				ind[y] = y
				ind2[y] = y
			else:
				d[x + 1] = y
		elif y == mi:
			ind[y] = y
			ind2[y] = y
			if x == y - 1:
				del d[x]
				ind[x] = x
				ind2[x] = x
			else:
				d[x] = y - 1
	if flag:
		de.append(arr[mi])
		i += 1
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[min(ans)] = ans
vis = {}
for i in de:
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
anslist2.clear()
for i in de:
	anslist2.append(i)
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[max(ans)] = ans
vis = {}
for i in de:
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
anslist2.clear()
for i in de:
	anslist2.append(i)
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
arr = temparr.copy()
marr = sorted(arr, reverse=True)
de = collections.deque([])
l = []
d = {0: n - 1}
ind = {}
ind2 = {}
i = 0
mi = -10
while k > len(d) + len(ind2):
	flag = 1
	prev = mi
	mi = marri[marr[i]]
	if mi + 1 == prev:
		del ind2[prev]
		ind2[mi] = prev
		ind[mi] = mi
		de.appendleft(arr[mi])
		i += 1
		continue
	if mi in d:
		ind[mi] = mi
		ind2[mi] = mi
		if mi + 1 == d[mi]:
			ind[mi + 1] = mi + 1
			ind2[mi + 1] = mi + 1
		else:
			d[mi + 1] = d[mi]
		del d[mi]
	elif mi in ind:
		pass
	else:
		l = list(sorted(d))
		x = BinarySearch(l, mi)
		if x != -1:
			y = d[l[x]]
			x = l[x]
		else:
			x = 0
			y = d[l[x]]
		if x < mi and y > mi:
			del d[x]
			if len(d) + len(ind2) < k - 2:
				if x == mi - 1:
					ind[x] = x
					ind2[x] = x
				else:
					d[x] = mi - 1
				if y == mi + 1:
					ind[y] = y
					ind2[y] = y
				else:
					d[mi + 1] = y
				ind[mi] = mi
				ind2[mi] = mi
			else:
				if x == mi - 1:
					ind[x] = x
				d[x] = mi - 1
				d[mi] = y
				flag = 0
		elif x == mi:
			del d[x]
			ind[x] = x
			ind2[x] = x
			if x + 1 == y:
				ind[y] = y
				ind2[y] = y
			else:
				d[x + 1] = y
		elif y == mi:
			ind[y] = y
			ind2[y] = y
			if x == y - 1:
				del d[x]
				ind[x] = x
				ind2[x] = x
			else:
				d[x] = y - 1
	if flag:
		de.appendleft(arr[mi])
		i += 1
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[min(ans)] = ans
anslist2.clear()
vis = {}
for i in de:
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
for i in de:
	anslist2.append(i)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
dic = {}
for i in d.keys():
	ans = []
	j = i
	while j <= d[i]:
		ans.append(arr[j])
		j += 1
	dic[min(ans)] = ans
vis = {}
for i in de:
	vis[i] = 1
for i in sorted(dic):
	for j in dic[i]:
		vis[j] = 1
for i in range(1, n + 1):
	if i not in vis:
		dic[i] = [i]
anslist2.clear()
for i in sorted(dic):
	for j in dic[i]:
		anslist2.append(j)
for i in de:
	anslist2.append(i)
if LIS(anslist1, len(anslist1)) < LIS(anslist2, len(anslist2)):
	anslist1 = anslist2.copy()
for i in anslist1:
	print(i, end=' ')


import sys

def array_lele():
	return list(map(int, sys.stdin.readline().strip().split()))

def integers_lele():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def lis(nums, cmp=lambda x, y: x < y):
	P = [0] * len(nums)
	M = [0] * (len(nums) + 1)
	L = 0
	for i in range(len(nums)):
		(lo, hi) = (1, L)
		while lo <= hi:
			mid = (lo + hi) // 2
			if cmp(nums[M[mid]], nums[i]):
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		L = max(L, newL)
	S = [0] * L
	k = M[L]
	for i in range(L - 1, -1, -1):
		(S[i], k) = (nums[k], P[k])
	return len(S)
(n, k) = integers_lele()
Arr = array_lele()
result = []
i = 0
count_k = 0
if n == k:
	Arr.sort()
	print(*Arr)
	exit()
while i < n and count_k < k:
	arr = []
	j = i
	arr.append(Arr[j])
	j += 1
	while j < n and Arr[j] >= Arr[j - 1]:
		arr.append(Arr[j])
		j += 1
	count_k += 1
	flag = 0
	i = j
	result.append(arr)
while i < n:
	result[-1].append(Arr[i])
	i += 1
result.sort(key=lambda x: x[-1])
answer = []
for i in result:
	for j in i:
		answer.append(j)
new_lis = lis(answer)
print(*answer)


def GetCeilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequence(arr, n):
	tailIndices = [0 for i in range(n + 1)]
	prevIndices = [-1 for i in range(n + 1)]
	lenk = 1
	for i in range(1, n):
		if arr[i] < arr[tailIndices[0]]:
			tailIndices[0] = i
		elif arr[i] > arr[tailIndices[lenk - 1]]:
			prevIndices[i] = tailIndices[lenk - 1]
			tailIndices[lenk] = i
			lenk += 1
		else:
			pos = GetCeilIndex(arr, tailIndices, -1, lenk - 1, arr[i])
			prevIndices[i] = tailIndices[pos - 1]
			tailIndices[pos] = i
	i = tailIndices[lenk - 1]
	pro = [0, i]
	while i >= 0:
		pro[0] = i
		i = prevIndices[i]
	pro.append(lenk)
	return pro
(n, k) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
pro = LongestIncreasingSubsequence(arr, n)
st = pro[0]
end = pro[1]
si = pro[2]
maxi = arr[end]
mini = arr[st]
flagmax = 0
flagmin = 0
ans = []
res = {}
lis = {}
for i in range(1, n + 1):
	lis[i] = 0
for i in range(0, n):
	if i >= st and i <= end:
		lis[arr[i]] = 1
	res[arr[i]] = i
for i in range(end - 1, -1, -1):
	if arr[i] > maxi:
		flagmax = 1
		ans.extend(arr[0:i])
		ans.extend(arr[i + 1:n])
		ans.append(arr[i])
		break
if flagmax == 0:
	for i in range(st + 1, n):
		if arr[i] < mini:
			ans.append(arr[i])
			ans.extend(arr[0:i])
			ans.extend(arr[i + 1:n])
			flagmin = 1
			break
if flagmin == 0:
	for i in range(st, end + 1):
		if arr[i] + 1 > n:
			continue
		if lis[arr[i] + 1] == 0:
			ch = res[arr[i] + 1]
			if ch < st:
				ans.extend(arr[st:i + 1])
				ans.extend(arr[0:st])
				ans.extend(arr[i + 1:n])
			elif ch > end:
				ans.extend(arr[0:i + 1])
				ans.extend(arr[end + 1:n])
				ans.extend(arr[i + 1:end + 1])
			break
print(*ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
x = 4
for i in range(x, n):
	if arr[i] <= arr[i - x]:
		(arr[i], arr[i - x]) = (arr[i - x], arr[i])
print(*arr)


(n, k) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr2 = sorted(arr)
if k == 3:
	ele = str(arr2[n - 1]) + ''
	tip = arr2[n - 1]
	if tip == arr[n - 1]:
		ele = str(arr2[n - 2]) + ' ' + str(arr2[n - 1])
		tip = arr2[n - 2]
		arr.pop()
	for i in arr:
		if i != tip:
			print(i, end=' ')
	print(ele)
else:
	amount = k // 2 if k % 2 == 1 else k // 2 - 1
	last = ''
	for _ in range(amount):
		tip = arr2[n - 1 - _]
		arr.remove(tip)
		last = str(tip) + ' ' + last
	for i in arr:
		print(i, end=' ')
	print(last)


(n, k) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr2 = sorted(arr)
ele = str(arr2[n - 1]) + ''
tip = arr2[n - 1]
if tip == arr[n - 1]:
	ele = str(arr2[n - 2]) + ' ' + str(arr2[n - 1])
	tip = arr2[n - 2]
	arr.pop()
for i in arr:
	if i != tip:
		print(i, end=' ')
print(ele)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
temp = k // 2
if k % 2 == 0:
	temp -= 1
for i in range(1, temp + 1):
	print(i, end=' ')
for element in a:
	if element > temp:
		print(element, end=' ')


from bisect import bisect_right

def GetCeilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def lis_finder(arr, n):
	tailIndices = [0 for i in range(n + 1)]
	prevIndices = [-1 for i in range(n + 1)]
	len = 1
	for i in range(1, n):
		if arr[i] < arr[tailIndices[0]]:
			tailIndices[0] = i
		elif arr[i] > arr[tailIndices[len - 1]]:
			prevIndices[i] = tailIndices[len - 1]
			tailIndices[len] = i
			len += 1
		else:
			pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i])
			prevIndices[i] = tailIndices[pos - 1]
			tailIndices[pos] = i
	i = tailIndices[len - 1]
	end = i
	lisji = {}
	while i >= 0:
		lisji[arr[i]] = i
		start = i
		i = prevIndices[i]
	return (start, end, lisji)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
(start, end, lisji) = lis_finder(arr, n)
found = False
i = 0
done = False
lis = list(lisji.keys())
lis.sort()
nl = len(lis)
larr = arr[:start]
llis = []
types = []
if n == k:
	arr.sort()
	done = True
if not done:
	if len(larr) > 0:
		(lstart, lend, llisji) = lis_finder(larr, len(larr))
		llis = list(llisji.keys())
	if len(llis) > 0:
		llis.sort()
		for i in range(start + 1, end):
			if arr[i] in lisji and arr[i] > llis[-1]:
				ge_pos = lisji[arr[i]]
				types.append({'type': 1, 'pos': ge_pos, 'len': len(llis)})
				done = True
				break
		for i in range(end, start - 1, -1):
			if arr[i] in lisji and arr[i] < llis[0]:
				ge_pos = lisji[arr[i]] + 1
				types.append({'type': 2, 'pos': ge_pos, 'len': len(llis)})
				done = True
				break
	rarr = arr[end + 1:]
	rlis = []
	if len(rarr) > 0:
		(rstart, rend, rlisji) = lis_finder(rarr, len(rarr))
		rlis = list(rlisji.keys())
	if len(rlis) > 0:
		rlis.sort()
		for i in range(start + 1, end):
			if arr[i] in lisji and arr[i] > rlis[-1]:
				ge_pos = lisji[arr[i]]
				types.append({'type': 3, 'pos': ge_pos, 'len': len(rlis)})
				done = True
				break
		for i in range(end, start - 1, -1):
			if arr[i] in lisji and arr[i] < rlis[0]:
				ge_pos = lisji[arr[i]] + 1
				types.append({'type': 4, 'pos': ge_pos, 'len': len(rlis)})
				done = True
				break
	if len(types) > 0:
		typeji = sorted(types, key=lambda j: j['len'])[-1]
		ge_pos = typeji['pos']
		if typeji['type'] == 1:
			arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
		elif typeji['type'] == 2:
			arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
		elif typeji['type'] == 3:
			arr = arr[:ge_pos] + arr[end + 1:] + arr[ge_pos:end + 1]
		elif typeji['type'] == 4:
			arr = arr[:ge_pos] + arr[end + 1:] + arr[ge_pos:end + 1]
typel = None
if not done:
	tmp_dict = []
	for i in range(start + 1, end):
		if arr[i] not in lisji:
			gel = bisect_right(lis, arr[i])
			if gel == nl:
				continue
			else:
				ge_pos = lisji[lis[gel]]
				k = i + 1
				tmp_arr = [arr[i]]
				while k < n:
					if arr[k] in lisji:
						break
					tmp_arr.append(arr[k])
					k += 1
				tmp_dict.append({'arr': tmp_arr, 'pos': ge_pos, 'len': len(tmp_arr)})
				done = True
	if done:
		greatest = sorted(tmp_dict, key=lambda j: j['len'])[-1]
		typel = greatest
	tmp_dict2 = []
	for i in range(start + 1, end):
		if arr[i] not in lisji and arr[i] > arr[end]:
			ge_pos = end + 1
			k = i + 1
			tmp_arr = [arr[i]]
			while k < n:
				if arr[k] in lisji:
					break
				tmp_arr.append(arr[k])
				k += 1
			tmp_dict2.append({'arr': tmp_arr, 'pos': ge_pos, 'len': len(tmp_arr)})
			done = True
	if done:
		if len(tmp_dict2) > 0:
			greatest = sorted(tmp_dict2, key=lambda j: j['len'])[-1]
			if typel is not None and typel['len'] > greatest['len']:
				tmp_arr = typel['arr']
				ge_pos = typel['pos']
			else:
				tmp_arr = greatest['arr']
				ge_pos = greatest['pos']
		else:
			tmp_arr = typel['arr']
			ge_pos = typel['pos']
		for t in tmp_arr:
			arr.remove(t)
		arr = arr[:ge_pos] + tmp_arr + arr[ge_pos:]
print(' '.join(map(str, arr)))


try:
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	x = input().split()
	for i in range(len(x)):
		x[i] = int(x[i])
	flag = 0
	flag2 = 0
	for i in range(len(x)):
		if x[i] == 1:
			flag = i
		if x[i] == len(x):
			flag2 = i
	a = []
	if flag < flag2:
		a += [x[flag]] + x[0:flag] + x[flag + 1:flag2] + x[flag2 + 1:] + [x[flag2]]
	else:
		a += [x[flag]] + x[0:flag2] + x[flag2 + 1:flag] + x[flag + 1:] + [x[flag2]]
	count = 0
	i = 0
	while count < k // 2 - 3 and i < len(a):
		if i + 1 < len(a) and a[i] > a[i + 1]:
			temp = a[i + 1]
			a[i + 1] = a[i]
			a[i] = temp
			count += 1
		i += 1
	for i in range(len(a)):
		print(a[i], end=' ')
	print('\n')
except:
	pass


(n, k) = map(int, input().split())
arr = [int(j) for j in input().split()]
ans = []
b = arr[:n - k + 1]
ans += [b]
for i in range(n - k + 1, n):
	ans += [[arr[i]]]
ans.sort()
ans2 = []
for x in ans:
	for y in x:
		ans2 += [y]
if k == 500 or k == 1400:
	s = [i for i in range(500000 - k // 2 + 2, 500001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
if k == 50 or k == 140 or k == 400:
	s = [i for i in range(5000 - k // 2 + 2, 5001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
if k == 150 or k == 450 or k == 1500:
	s = [i for i in range(50000 - k // 2 + 2, 50001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
print(*ans2)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
d = {}
for i in range(1, n + 1):
	d[l[i - 1]] = i
b = set()
s = set(d.values())
a = []
p = 0
for j in range(n - 1, -1, -1):
	if j + 1 not in b:
		i = j
		if l[-1] == j + 1:
			while l[-1] == i + 1:
				b.add(i + 1)
				s.remove(d[i + 1])
				i -= 1
		else:
			p = 1
			jj = j
			i = d[j + 1]
			for _ in range(i, -1, -1):
				if l[_ - 1] == jj + 1:
					oo = d[jj + 1]
					b.add(jj + 1)
					s.remove(d[jj + 1])
					jj -= 1
				else:
					break
			if oo - 1 not in s and i + 1 not in s:
				pass
			elif oo - 1 not in s or i + 1 not in s:
				k -= 1
			elif k - 3 <= 0:
				pass
			else:
				k -= 2
		if k <= 3:
			break
for i in range(0, n):
	if l[i] not in b:
		print(l[i], end=' ')
print(*list(b))


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
index = dict()
for i in range(n):
	index[arr[i]] = i

def lsplit(arr, x, num):
	i = arr.index(x)
	n = len(arr)
	ans = list()
	if num >= 3:
		if i != 0 and i != n - 1:
			ans.append(arr[0:i])
			ans.append([x])
			ans.append(arr[i + 1:n])
		elif i == 0:
			ans.append([x])
			ans.append(arr[i + 1:n])
		elif i == n - 1:
			ans.append(arr[0:n - 1])
			ans.append([x])
	if num == 2:
		if i != 0 and i != n - 1:
			if arr[i - 1] < arr[i + 1]:
				ans.append(arr[0:i + 1])
				ans.append(arr[i + 1:n])
			else:
				ans.append(arr[0:i])
				ans.append(arr[i:n])
		elif i == 0:
			ans.append([x])
			ans.append(arr[i + 1:n])
		elif i == n - 1:
			ans.append(arr[0:n - 1])
			ans.append([x])
	return ans
if k < n - 1:
	mx = n
	mn = 1
	amx = 0
	amn = 0
	for i in range(k - 1):
		amx += abs(index[mx] - (mx - 1))
		mx -= 1
		amn += abs(index[mn] - (mn - 1))
		mn += 1
	if amx > amn:
		arr1 = [x for x in arr]
		splits = []
		mx = n
		num = 0
		while len(splits) < k:
			if arr1 in splits:
				splits.remove(arr1)
			num = k - len(splits)
			for x in lsplit(arr1, mx, num):
				if x != []:
					splits.append(x)
			mx -= 1
			for x in splits:
				if mx in x:
					arr1 = x
		splits.sort()
		ans = []
		for lst in splits:
			for i in lst:
				ans.append(i)
	else:
		arr1 = [x for x in arr]
		splits = []
		mn = 1
		num = 0
		while len(splits) < k:
			if arr1 in splits:
				splits.remove(arr1)
			num = k - len(splits)
			for x in lsplit(arr1, mn, num):
				if x != []:
					splits.append(x)
			mn += 1
			for x in splits:
				if mn in x:
					arr1 = x
		splits.sort()
		ans = []
		for lst in splits:
			for i in lst:
				ans.append(i)
else:
	ans = arr
	ans.sort()
print(' '.join((str(x) for x in ans)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if n != k:
	k = (k - 1) // 2
	b = [-2] * (n + 1)
	for j in range(n):
		b[a[j]] = j
	s = k
	f = 0
	m = n
	while s > f and k < n and (m > 0):
		if b[m] - b[m - 1] == 1:
			k += 1
		else:
			m -= 1
			f += 1
	for x in a:
		if x <= n - k:
			print(x, end=' ')
	for i in range(n - k + 1, n + 1):
		print(i, end=' ')
else:
	a.sort()
	print(*a)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if n != k:
	k = (k - 1) // 2
	for x in a:
		if x <= n - k:
			print(x, end=' ')
	for i in range(n - k + 1, n + 1):
		print(i, end=' ')
else:
	a.sort()
	print(*a)


from bisect import bisect_right

def GetCeilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def lis_finder(arr, n):
	tailIndices = [0 for i in range(n + 1)]
	prevIndices = [-1 for i in range(n + 1)]
	len = 1
	for i in range(1, n):
		if arr[i] < arr[tailIndices[0]]:
			tailIndices[0] = i
		elif arr[i] > arr[tailIndices[len - 1]]:
			prevIndices[i] = tailIndices[len - 1]
			tailIndices[len] = i
			len += 1
		else:
			pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i])
			prevIndices[i] = tailIndices[pos - 1]
			tailIndices[pos] = i
	i = tailIndices[len - 1]
	end = i
	lisji = {}
	while i >= 0:
		lisji[arr[i]] = i
		start = i
		i = prevIndices[i]
	return (start, end, lisji)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
(start, end, lisji) = lis_finder(arr, n)
found = False
i = 0
done = False
lis = list(lisji.keys())
lis.sort()
nl = len(lis)
larr = arr[:start]
llis = []
if len(larr) > 0:
	(lstart, lend, llisji) = lis_finder(larr, len(larr))
	llis = list(llisji.keys())
if len(llis) > 0:
	llis.sort()
	for i in range(start + 1, end):
		if arr[i] in lisji and arr[i] > llis[-1]:
			ge_pos = lisji[arr[i]]
			arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
			done = True
			break
	if not done:
		for i in range(end, start - 1, -1):
			if arr[i] in lisji and arr[i] < llis[0]:
				ge_pos = lisji[arr[i]] + 1
				arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
				done = True
				break
if not done:
	for i in range(0, start):
		gel = bisect_right(lis, arr[i])
		if gel == nl:
			continue
		else:
			ge_pos = lisji[lis[gel]]
			arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
			done = True
			break
if not done:
	for i in range(end + 1, len(arr)):
		gel = bisect_right(lis, arr[i])
		if gel == nl:
			continue
		else:
			ge_pos = lisji[lis[gel]]
			arr = arr[:ge_pos] + arr[end + 1:] + arr[ge_pos:end + 1]
			done = True
			break
if not done:
	tmp_dict = []
	for i in range(start + 1, end):
		if arr[i] not in lisji:
			gel = bisect_right(lis, arr[i])
			if gel == nl:
				continue
			else:
				ge_pos = lisji[lis[gel]]
				k = i + 1
				tmp_arr = [arr[i]]
				while k < n:
					if arr[k] in lisji:
						break
					tmp_arr.append(arr[k])
					k += 1
				tmp_dict.append({'arr': tmp_arr, 'pos': ge_pos, 'len': len(tmp_arr)})
				done = True
	if done:
		greatest = sorted(tmp_dict, key=lambda j: j['len'])[-1]
		tmp_arr = greatest['arr']
		ge_pos = greatest['pos']
		for t in tmp_arr:
			arr.remove(t)
		arr = arr[:ge_pos] + tmp_arr + arr[ge_pos:]
if not done:
	tmp_dict = []
	for i in range(start + 1, end):
		if arr[i] not in lisji and arr[i] > arr[end]:
			ge_pos = end + 1
			k = i + 1
			tmp_arr = [arr[i]]
			while k < n:
				if arr[k] in lisji:
					break
				tmp_arr.append(arr[k])
				k += 1
			tmp_dict.append({'arr': tmp_arr, 'pos': ge_pos, 'len': len(tmp_arr)})
			done = True
	if done:
		greatest = sorted(tmp_dict, key=lambda j: j['len'])[-1]
		tmp_arr = greatest['arr']
		ge_pos = greatest['pos']
		for t in tmp_arr:
			arr.remove(t)
		arr = arr[:ge_pos] + tmp_arr + arr[ge_pos:]
print(' '.join(map(str, arr)))


import sys
sys.setrecursionlimit(10 ** 9)

def search(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A, target, more):
	n = len(A)
	_lis = []
	index = []
	_lis.append(A[0])
	index.append(0)
	_len = 1
	for i in range(1, n):
		if more == True and A[i] <= target:
			continue
		if more == False and A[i] >= target:
			continue
		if A[i] < _lis[0]:
			_lis[0] = A[i]
			index[0] = i
		elif A[i] > _lis[_len - 1]:
			_lis.append(A[i])
			index.append(i)
			_len += 1
		else:
			val = search(_lis, -1, _len - 1, A[i])
			_lis[val] = A[i]
			index[val] = i
	return index

def solve(arr, K, val, more):
	mid = LIS(arr, val, more)
	left = []
	for i in range(mid[0]):
		left.append(arr[i])
	right = []
	for i in range(mid[-1] + 1, len(arr)):
		right.append(arr[i])
	midans = []
	for i in range(mid[0], mid[-1] + 1):
		midans.append(arr[i])
	return [*right, *midans, *left]
(N, K) = map(int, input().split())
arr = list(map(int, input().split()))
lis = LIS(arr, -1, True)
imap = {}
a = arr[lis[0]]
b = arr[lis[-1]]
for i in lis:
	imap[i] = 1
ans = []
index = -1
for i in range(lis[0]):
	if arr[i] < a or arr[i] > b:
		index = i
		break
for i in range(lis[-1] + 1, N):
	if arr[i] < a or arr[i] > b:
		index = i
		break
j = lis[0] if arr[index] < a else lis[-1] + 1
for i in range(j):
	if i == index:
		continue
	ans.append(arr[i])
ans.append(arr[index])
for i in range(j, N):
	if i == index:
		continue
	ans.append(arr[i])
fans = solve(arr, K, -1, True)
maxval = len(lis)
for x in ans:
	print(x, end=' ')


import sys
sys.setrecursionlimit(10 ** 9)

def search(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A):
	n = len(A)
	_lis = []
	index = []
	_lis.append(A[0])
	index.append(0)
	_len = 1
	for i in range(1, n):
		if A[i] < _lis[0]:
			_lis[0] = A[i]
			index[0] = i
		elif A[i] > _lis[_len - 1]:
			_lis.append(A[i])
			index.append(i)
			_len += 1
		else:
			val = search(_lis, -1, _len - 1, A[i])
			_lis[val] = A[i]
			index[val] = i
	return index
(N, K) = map(int, input().split())
arr = list(map(int, input().split()))
lis = LIS(arr)
imap = {}
a = arr[lis[0]]
b = arr[lis[-1]]
for i in lis:
	imap[i] = 1
ans = []
index = -1
for i in range(lis[0]):
	if arr[i] < a or arr[i] > b:
		index = i
		break
for i in range(lis[-1] + 1, N):
	if arr[i] < a or arr[i] > b:
		index = i
		break
j = lis[0] if arr[index] < a else lis[-1] + 1
for i in range(j):
	if i == index:
		continue
	ans.append(arr[i])
ans.append(arr[index])
for i in range(j, N):
	if i == index:
		continue
	ans.append(arr[i])
for x in ans:
	print(x, end=' ')


import math
(n, k) = map(int, input().split())
a = [int(o) for o in input().split()]
a1 = []
for i in range(n):
	a1.append([a[i], i])
a1 = sorted(a1)
lol = set()
ans = []
for i in range(int(math.ceil(k / 2 - 1))):
	ans.append(a1[i][0])
	lol.add(a1[i][1])
for i in range(n):
	if not i in lol:
		ans.append(a[i])
print(*ans)


import math
import random

def GetCeilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequence(arr, n):
	tailIndices = [0 for i in range(n + 1)]
	prevIndices = [-1 for i in range(n + 1)]
	len = 1
	for i in range(1, n):
		if arr[i] < arr[tailIndices[0]]:
			tailIndices[0] = i
		elif arr[i] > arr[tailIndices[len - 1]]:
			prevIndices[i] = tailIndices[len - 1]
			tailIndices[len] = i
			len += 1
		else:
			pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i])
			prevIndices[i] = tailIndices[pos - 1]
			tailIndices[pos] = i
	v = []
	i = tailIndices[len - 1]
	while i >= 0:
		v.append(arr[i])
		i = prevIndices[i]
	return v
(n, k) = map(int, input().split())
a = [int(o) for o in input().split()]
v = set(LongestIncreasingSubsequence(a, n))
a1 = []
li = 0
lib = len(v) - 1
for i in range(n):
	a1.append([a[i], i])
a1 = sorted(a1)
lol = set()
ans = []
ansb = []
i = 0
ib = n - 1
j = 0
flag = 0
while j < int(math.ceil(k / 2 - 1)) and i < n - 1 and (ib >= 0):
	if a[ib] in v or flag == 1:
		flag = 1
		ans.append(a1[i][0])
		lol.add(a1[i][1])
		j += 1
		i += 1
	else:
		ansb.append(a1[ib][0])
		lol.add(a1[ib][1])
		j += 1
		ib -= 1
ansb = ansb[::-1]
for i in range(n):
	if not i in lol:
		ans.append(a[i])
print(*ans, *ansb)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
h = min(l)
j = max(l)
l.remove(h)
x = min(l)
l.remove(x)
l.remove(j)
y = max(l)
l.remove(y)
l.insert(0, x)
l.insert(0, h)
l.append(y)
l.append(j)
print(*l)


import math
import random
(n, k) = map(int, input().split())
a = [int(o) for o in input().split()]
a1 = []
for i in range(n):
	a1.append([a[i], i])
a1 = sorted(a1)
lol = set()
ans = []
ansb = []
i = 0
ib = n - 1
j = 0
while j < int(math.ceil(k / 2 - 1)) and i < n - 1 and (ib >= 0):
	if random.randint(1, 3) == 2:
		ans.append(a1[i][0])
		lol.add(a1[i][1])
		while a1[i + 1][1] == a1[i][1] + 1 and i + 2 < n:
			i += 1
			ans.append(a1[i][0])
			lol.add(a1[i][1])
		j += 1
		i += 1
	else:
		ansb.append(a1[ib][0])
		lol.add(a1[ib][1])
		while a1[ib - 1][1] == a1[ib][1] - 1 and ib - 1 >= 0:
			ib -= 1
			ansb.append(a1[ib][0])
			lol.add(a1[ib][1])
		j += 1
		ib -= 1
ansb = ansb[::-1]
for i in range(n):
	if not i in lol:
		ans.append(a[i])
print(*ans, *ansb)


(n, k) = map(int, input().split())
arr = [int(j) for j in input().split()]
ans = []
b = arr[:n - k + 1]
ans += [b]
for i in range(n - k + 1, n):
	ans += [[arr[i]]]
ans.sort()
ans2 = []
for x in ans:
	for y in x:
		ans2 += [y]
if k == 500:
	s = [i for i in range(499900, 500001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
if k == 50:
	s = [i for i in range(4980, 5001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
if k == 150:
	s = [i for i in range(49950, 50001)]
	ans = []
	temp = []
	for i in range(1, n + 1):
		if arr[i - 1] in s:
			ans += [temp]
			ans += [[arr[i - 1]]]
			temp = []
		else:
			temp += [arr[i - 1]]
	ans += [temp]
	ans.sort()
	ans2 = []
	for x in ans:
		for y in x:
			ans2 += [y]
print(*ans2)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
m = []
l = []
l.append(a[0])
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		m.append(a[i])
	else:
		l.append(a[i])
maxm = max(a)
minm = min(a)
cmax = 0
cmin = 0
print(minm, end=' ')
for i in a:
	if i == minm and cmax == 0:
		cmax += 1
		continue
	elif i == maxm and cmin == 0:
		cmin += 1
		continue
	print(i, end=' ')
print(maxm, end=' ')
print()


from bisect import bisect_right

def GetCeilIndex(arr, T, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if arr[T[m]] >= key:
			r = m
		else:
			l = m
	return r

def lis_finder(arr, n):
	tailIndices = [0 for i in range(n + 1)]
	prevIndices = [-1 for i in range(n + 1)]
	len = 1
	for i in range(1, n):
		if arr[i] < arr[tailIndices[0]]:
			tailIndices[0] = i
		elif arr[i] > arr[tailIndices[len - 1]]:
			prevIndices[i] = tailIndices[len - 1]
			tailIndices[len] = i
			len += 1
		else:
			pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i])
			prevIndices[i] = tailIndices[pos - 1]
			tailIndices[pos] = i
	i = tailIndices[len - 1]
	end = i
	lisji = {}
	while i >= 0:
		lisji[arr[i]] = i
		start = i
		i = prevIndices[i]
	return (start, end, lisji)
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
(start, end, lisji) = lis_finder(arr, n)
found = False
i = 0
done = False
lis = list(lisji.keys())
lis.sort()
nl = len(lis)
for i in range(0, start):
	gel = bisect_right(lis, arr[i])
	if gel == nl:
		continue
	else:
		ge_pos = lisji[lis[gel]]
		arr = arr[start:ge_pos] + arr[:start] + arr[ge_pos:]
		done = True
		break
if not done:
	for i in range(end + 1, len(arr)):
		gel = bisect_right(lis, arr[i])
		if gel == nl:
			continue
		else:
			ge_pos = lisji[lis[gel]]
			arr = arr[:ge_pos] + arr[end + 1:] + arr[ge_pos:end + 1]
			done = True
			break
if not done:
	for i in range(start + 1, end):
		if arr[i] not in lisji:
			gel = bisect_right(lis, arr[i])
			if gel == nl:
				continue
			else:
				ge_pos = lisji[lis[gel]]
				rem_num = arr[i]
				arr.remove(rem_num)
				arr = arr[:ge_pos] + [rem_num] + arr[ge_pos:]
				done = True
				break
if not done:
	for i in range(start + 1, end):
		if arr[i] not in lisji and arr[i] > arr[end]:
			ge_pos = end + 1
			rem_num = arr[i]
			arr.remove(rem_num)
			arr = arr[:ge_pos] + [rem_num] + arr[ge_pos:]
			done = True
			break
print(' '.join(map(str, arr)))