Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$-th integer represents the color of the $i$-th pixel in the image. The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key. In order to preserve image details, the size of a group must not be greater than $k$, and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right. 

 [Image] 

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 256$), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq 255$), where $p_i$ is the color of the $i$-th pixel.


-----Output-----

Print $n$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter.


-----Examples-----
Input
4 3
2 14 3 4

Output
0 12 3 3

Input
5 2
0 2 1 255 254

Output
0 1 1 254 254



-----Note-----

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$, with group key $0$.

Color $14$ belongs to the group $[12,14]$, with group key $12$.

Colors $3$ and $4$ belong to group $[3, 5]$, with group key $3$.

Other groups won't affect the result so they are not listed here.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Game theory

Greedy algorithms


Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
c = [-1] * 256
ans = [0] * n
for i in range(n):
	if c[a[i]] == -1:
		for j in range(a[i], max(-1, a[i] - k), -1):
			if c[j] != -1:
				if c[j] + k > a[i]:
					c[a[i]] = c[j]
				else:
					c[a[i]] = j + 1
				break
		if c[a[i]] == -1:
			c[a[i]] = max(0, a[i] - k + 1)
		for xx in range(c[a[i]], a[i]):
			c[xx] = c[a[i]]
	ans[i] = str(c[a[i]])
print(' '.join(ans))


[n, k] = map(int, input().strip().split())
pis = list(map(int, input().strip().split()))
import sys
if k == 1:
	print(' '.join(map(str, pis)))
	return
N = 256
gamma = [-1 for _ in range(N)]
done = [False for _ in range(N)]
revdone = [False for _ in range(N)]
notset = 256
pends = {}

def get_bounds(i):
	try:
		l = N - 1 - revdone.index(True, N - 1 - i) + 1
	except ValueError:
		l = 0
	try:
		r = done.index(True, i) - 1
	except ValueError:
		r = N - 1
	return (l, r)

def set_gamma(l, r, v):
	for i in range(l, r + 1):
		gamma[i] = v
		done[i] = True
		revdone[N - 1 - i] = True
for p in pis:
	if not done[p]:
		(lb, rb) = get_bounds(p)
		if lb > 0 and lb - 1 in pends and (lb - 1 + pends[lb - 1] >= p):
			l = lb
			r = p
			set_gamma(l, r, gamma[lb - 1])
			if r - l + 1 < pends[lb - 1]:
				pends[r] = pends[lb - 1] - (r - l + 1)
			del pends[lb - 1]
		else:
			l = max(p - k + 1, lb)
			r = p
			set_gamma(l, r, l)
			if r - l + 1 < k:
				pends[p] = k - (r - l + 1)
		notset -= r - l + 1
		if notset == 0:
			break
if notset > 0:
	for i in range(N):
		if gamma[i] < 0:
			(l, r) = get_bounds(i)
			set_gamma(l, min(l + k - 1, r), l)
print(' '.join((str(gamma[p]) for p in pis)))


(n, k) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
colors = [-1 for i in range(256)]
for i in range(len(p)):
	if colors[p[i]] == -1:
		stack = [p[i]]
		val = p[i]
		for j in range(1, k):
			if p[i] - j < 0:
				break
			elif colors[p[i] - j] != -1 and p[i] - colors[p[i] - j] >= k:
				break
			elif colors[p[i] - j] != -1:
				val = colors[p[i] - j]
				break
			else:
				val = p[i] - j
				stack.append(p[i] - j)
		else:
			val = max(0, p[i] - k + 1)
		while len(stack):
			colors[stack.pop()] = val
	print(colors[p[i]], end=' ')


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve():
	(n, k) = li()
	p = li()
	groups = [-1] * 256
	newar = [-1] * n
	for i in range(n):
		color = p[i]
		j = color
		if groups[color] != -1:
			newar[i] = groups[color]
			continue
		while j > 0:
			if groups[j] != -1:
				break
			if color - j + 1 == k:
				break
			j -= 1
		if groups[j] == -1:
			for h in range(j, color + 1):
				groups[h] = j
			newar[i] = groups[color]
			continue
		if color - j < k:
			alreadySize = j - groups[j] + 1
			if alreadySize + color - j <= k:
				for h in range(j + 1, color + 1):
					groups[h] = groups[h - 1]
				newar[i] = groups[color]
				continue
			else:
				for h in range(j + 1, color + 1):
					groups[h] = j + 1
				newar[i] = groups[color]
				continue
		else:
			for h in range(j + 1, color + 1):
				groups[h] = j + 1
			newar[i] = groups[color]
			continue
	print(*newar)
t = 1
for _ in range(t):
	solve()


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
arr = [[] for i in range(256)]
ans = []
for i in p:
	j = i
	if len(arr[i]) == 0:
		c = 0
		while c < k and j >= 0:
			if len(arr[j]) + c > k:
				break
			if len(arr[j]) != 0:
				arr[i].extend(arr[j])
				break
			arr[j] = arr[i]
			arr[j].append(j)
			j -= 1
			c += 1
		arr[i].sort()
	ans.append(arr[i][0])
print(*ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
par = [i for i in range(260)]
path = [-1 for i in range(260)]
for i in range(n):
	j = arr[i]
	if path[j] >= 0:
		par[j] = par[path[j]]
		continue
	jump = 1
	while j > 0 and path[j] == -1 and (jump < k):
		path[j] = arr[i]
		j -= 1
		jump += 1
	if arr[i] - par[j] + 1 <= k:
		par[arr[i]] = par[j]
		path[j] = arr[i]
	else:
		par[arr[i]] = par[j + 1]
for i in range(n):
	print(par[arr[i]], end=' ')
print()


(n, k) = map(int, input().split())
ps = list(map(int, input().split()))
if k == 1:
	print(' '.join([str(i) for i in ps]))
	return
g = [None for i in range(256)]
f = [None for i in range(256)]
ans = []
for i in range(n):
	p = ps[i]
	if g[p] is not None:
		ans.append(g[p])
		f[p] = 1
	else:
		gb = 0
		for j in range(1, k):
			ind = p - j
			if f[ind] is not None:
				gb = ind + 1
				break
			if ind <= 0:
				break
			if j == k - 1:
				gb = ind
		ans.append(gb)
		for j in range(k):
			if gb + j >= 256:
				break
			if f[gb + j] is None:
				g[gb + j] = gb
			else:
				break
		f[gb] = 1
		f[p] = 1
print(' '.join([str(i) for i in ans]))


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
val = [-1] * 256
val[0] = 0
for i in range(0, n):
	if val[arr[i]] > -1:
		print(val[arr[i]], end=' ')
	else:
		flag = 0
		for j in range(1, k):
			if val[arr[i] - j] > -1:
				if arr[i] - val[arr[i] - j] < k:
					for p in range(arr[i] - j + 1, arr[i] + 1):
						val[p] = val[arr[i] - j]
				else:
					for t in range(1, j + 1):
						val[arr[i] - t + 1] = arr[i] - j + 1
				print(val[arr[i]], end=' ')
				flag = 1
				break
		if flag == 0:
			for j in range(0, k):
				val[arr[i] - j] = arr[i] - k + 1
			print(val[arr[i]], end=' ')


(n, k) = map(int, input().strip().split())
data = map(int, input().strip().split())
sol = []
mapping = [(-1, 1000)] * 256
for x in data:
	if mapping[x][0] == -1:
		for i in range(max(x - k + 1, 0), x + 1):
			if mapping[i][0] == -1:
				if i > 0 and mapping[i - 1][1] + (x - i + 1) <= k:
					p = mapping[i - 1][1] + 1
					for j in range(i, x + 1):
						mapping[j] = (mapping[i - 1][0], p)
						p += 1
				else:
					p = 1
					for j in range(i, x + 1):
						mapping[j] = (i, p)
						p += 1
				break
	sol.append(mapping[x][0])
print(' '.join(map(str, sol)))


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
maps = []
for _ in range(256):
	maps.append(['empty', 0])
output = []
for innum in l:
	if maps[innum][0] == 'chosen':
		outnum = maps[innum][1]
	elif maps[innum][0] == 'potential':
		outnum = maps[innum][1]
		i = innum
		while i >= 0 and maps[i][0] == 'potential':
			maps[i] = ['chosen', outnum]
			i -= 1
	else:
		i = innum
		while i >= 0 and i >= innum - (k - 1) and (maps[i][0] != 'chosen'):
			i -= 1
		i += 1
		outnum = i
		for j in range(outnum, innum + 1):
			maps[j] = ['chosen', outnum]
		if innum < 255:
			for j in range(innum + 1, min(256, outnum + k)):
				if maps[j][0] != 'chosen':
					maps[j] = ['potential', outnum]
	output.append(str(outnum))
print(' '.join(output))


def main():
	(n, k) = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]
	p = [-1] * 256
	p[0] = 0
	for x in a:
		if p[x] < 0:
			for y in range(x - 1, max(-1, x - k), -1):
				if p[y] >= 0:
					if p[y] + k > x:
						p[x] = p[y]
					else:
						p[x] = p[y + 1] = y + 1
					break
			if p[x] < 0:
				p[x] = p[x - k + 1] = x - k + 1
	b = [p[x] for x in a]
	print(' '.join(map(str, b)))
main()


(n, k) = list(map(int, input().split()))
p = list(map(int, input().split()))
processed = set()
color = {}
length = {}
ans = []

def exists(p, elt, d):
	for e in p:
		if e > elt:
			if e <= elt + d:
				return True
			elif e - d <= elt + d:
				return False
	return False

def exists2(p, elt, d):
	for e in p:
		if e > elt:
			if e <= elt + d:
				return False
			elif e - d <= elt + d:
				return [True, e - d]
	return False
for i in range(n):
	elt = p[i]
	if elt in processed:
		ans.append(color[elt])
	else:
		processed.add(elt)
		new = 1
		run = True
		for j in range(1, k):
			if elt - j < 0:
				break
			elif elt - j not in processed:
				processed.add(elt - j)
				new += 1
			elif length[elt - j] + new <= k:
				for i2 in range(length[elt - j] + new):
					color[elt - i2] = color[elt - j]
				length[elt] = length[elt - j] + new
				run = False
				break
			else:
				break
		if run:
			for j in range(new):
				color[elt - j] = elt - new + 1
			length[elt] = new
s = str(color[p[0]])
for elt in p[1:]:
	s += ' ' + str(color[elt])
print(s)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
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')
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
r = [-1] * 256
for i in p:
	for u in range(i, max(i - k, -1), -1):
		if r[u] >= 0:
			u += 1
			break
	if u <= i:
		if u > 0 and r[u - 1] + k > i:
			r[i] = r[u - 1]
		else:
			for j in range(u, i + 1):
				r[j] = u
	print(r[i])


R = lambda : map(int, input().split())
(n, k) = R()
a = list(range(0, 257))
v = [1] * 257
for p in R():
	if v[p]:
		t = p
		while t >= 0 and p - a[t] <= k - 1:
			t -= 1
		t += 1
		for i in range(t, p + 1):
			a[i] = a[t]
			v[i] = 0
	print(a[p], end=' ')


(n, k) = list(map(int, input().split()))
P = list(map(int, input().split()))
parent = list(range(256))
sz = [1] * 256

def rt(x):
	if x != parent[x]:
		parent[x] = rt(parent[x])
	return parent[x]

def u(rx, ry):
	parent[ry] = rx
	sz[rx] += sz[ry]
ans = [0] * n
for (i, p) in enumerate(P):
	rx = rt(p)
	while rx > 0 and sz[rx] + sz[rt(rx - 1)] <= k:
		u(rt(rx - 1), rx)
		rx = rt(p)
	ans[i] = rt(p)
print(' '.join(map(str, ans)))


(n, k) = [int(x) for x in input().split()]
ps = [int(x) for x in input().split()]
mapping = [-1 for _ in range(256)]
res = []
for p in ps:
	if mapping[p] == -1:
		j = p - k + 1
		while j < 0 or (mapping[j] != -1 and mapping[j] + k <= p):
			j += 1
		for i in range(j, p + 1):
			mapping[i] = j
	res.append(mapping[p])
print(' '.join(map(str, res)))


a = [0 for i in range(0, 256)]
(n, k) = input().split(' ')
k = int(k)
for c in input().split(' '):
	c = int(c)
	if a[c] != 0:
		print(a[c] - 1, end=' ')
	else:
		for x in range(c, c - k, -1):
			if a[x] == 0:
				i = x
			else:
				if c - a[x] + 1 < k:
					i = a[x] - 1
				break
			if x == 0:
				break
		for x in range(int(i), c + 1):
			a[x] = i + 1
		print(i, end=' ')


def getIntList():
	return list(map(int, input().split()))
(n, k) = getIntList()
p = getIntList()
choosed = [False] * 256
left = [i for i in range(256)]
for (i, x) in enumerate(p):
	if not choosed[x]:
		best = x
		for j in range(x - 1, max(-1, x - k), -1):
			if not choosed[j]:
				best = j
			else:
				if x - left[j] < k:
					best = left[j]
				break
		for j in range(best, x + 1):
			choosed[j] = True
			left[j] = best
	p[i] = left[x]
print(' '.join(map(str, p)))


import sys
(n, k) = list(map(int, next(sys.stdin).rstrip().split()))
xs = list(map(int, next(sys.stdin).rstrip().split()))
mapka = {}
lengths = {}
result = []
for x in xs:
	if x in mapka:
		result.append(mapka[x])
	else:
		left = max(0, x - k + 1)
		range_potential = x - left
		for i in range(range_potential, -1, -1):
			potential_left = x - i
			if potential_left not in mapka:
				result.append(potential_left)
				for y in range(potential_left, x + 1):
					mapka[y] = potential_left
				lengths[potential_left] = x - potential_left + 1
				break
			elif lengths[mapka[potential_left]] + (x - potential_left) <= k:
				result.append(mapka[potential_left])
				for y in range(mapka[potential_left] + lengths[mapka[potential_left]], x + 1):
					mapka[y] = mapka[potential_left]
					lengths[mapka[potential_left]] += 1
				break
print(' '.join(map(str, result)))


(n, k) = map(int, input().split())
l1 = list(map(int, input().split()))
assigned = {}
result = [0] * n
i = 0
for i in range(n):
	flag = 0
	x = k
	if l1[i] not in assigned:
		temp = l1[i]
		to_assign = []
		while temp >= 0 and x > 0 and (temp not in assigned):
			to_assign.append(temp)
			x -= 1
			temp -= 1
		if temp in assigned:
			if assigned[temp][1] + len(to_assign) <= k:
				for item in to_assign:
					assigned[item] = (assigned[temp][0], assigned[temp][1] + len(to_assign))
			else:
				y = min(to_assign)
				for item in to_assign:
					assigned[item] = (y, len(to_assign))
		else:
			y = min(to_assign)
			for item in to_assign:
				assigned[item] = (y, len(to_assign))
	result[i] = assigned[l1[i]][0]
print(*result, sep=' ')


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def main():
	(n, k) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	t = []
	g = {}
	for x in p:
		if x in g:
			t.append(g[x])
			continue
		kk = x - 1
		while True:
			if kk in g:
				if x - g[kk] < k:
					ttt = g[kk]
				else:
					ttt = kk + 1
				for i in range(kk + 1, x + 1):
					g[i] = ttt
				t.append(g[x])
				break
			elif kk < 0 or x - kk == k:
				for i in range(kk + 1, x + 1):
					g[i] = kk + 1
				t.append(g[x])
				break
			kk -= 1
	print(' '.join((str(x) for x in t)))
main()


def solve():
	(num_pixels, max_group_size) = (int(x) for x in input().split())
	pixels = [int(x) for x in input().split()]
	groups = [None for _ in range(256)]
	for pixel in pixels:
		if groups[pixel] is None:
			smallest_of_group = pixel
			while smallest_of_group >= 0 and smallest_of_group > pixel - max_group_size and (groups[smallest_of_group] is None):
				smallest_of_group -= 1
			if smallest_of_group >= 0 and groups[smallest_of_group] is not None and (pixel - groups[smallest_of_group] + 1 <= max_group_size):
				group_color = groups[smallest_of_group]
			else:
				group_color = smallest_of_group + 1
			smallest_of_group += 1
			for color in range(smallest_of_group, pixel + 1):
				groups[color] = group_color
	print(*(groups[pixel] for pixel in pixels))
solve()


(n, k) = map(int, input().split())
p = map(int, input().split())
ans = [0 for i in range(n)]
f = [-1 for i in range(256)]
i = -1
for x in p:
	i += 1
	if f[x] < 0:
		l = x
		while l > 0 > f[l - 1] and x - l < k - 1:
			l -= 1
		if l > 0 and x - f[l - 1] < k and (f[l - 1] >= 0):
			f[x] = f[l - 1]
		else:
			f[x] = l
		for j in range(l, x):
			f[j] = f[x]
	ans[i] = f[x]
for x in ans:
	print(x, end=' ')


(N, K) = input().split()
(N, K) = (int(N), int(K))
P = [int(x) for x in input().split()]
A = [None] * 256
A[0] = 0
for i in range(N):
	pn = P[i]
	if A[pn] is None:
		for j in range(K - 1, -1, -1):
			if pn < j:
				continue
			if A[pn - j] is None:
				A[pn - j] = pn - j
				break
			elif A[pn - j] + K - 1 >= pn:
				break
		for jj in range(j, -1, -1):
			A[pn - jj] = A[pn - j]
print(*[A[P[i]] for i in range(N)])


(n, k) = [int(x) for x in input().split()]
ns = [int(x) for x in input().split()]
done = [None] * 256
ans = [None] * n
for i in range(n):
	c = ns[i]
	if done[c] == None:
		j = c
		while True:
			if j < 0 or c - j >= k or (done[j] != None and done[j] != -1):
				break
			j -= 1
		j += 1
		for kk in range(k):
			if kk + j >= 256 or (done[kk + j] != None and done[kk + j] != -1):
				break
			if kk + j <= c:
				done[kk + j] = j
			else:
				done[kk + j] = -1
	elif done[c] == -1:
		j = c
		while True:
			if done[j] != None and done[j] != -1:
				break
			j -= 1
		a = done[j]
		for kk in range(j, c + 1):
			done[kk] = a
	else:
		pass
	ans[i] = done[c]
ans = [str(x) for x in ans]
print(' '.join(ans))


from bisect import bisect_left, bisect_right

def tuple_input(type):
	return map(type, input().strip().split())
(n, k) = tuple_input(int)
p = list(tuple_input(int))
s = [-1] * 256
seg = dict()
for i in range(n):
	if s[p[i]] == -1:
		lef = p[i]
		while p[i] - lef < k and lef >= 0 and (s[lef] == -1):
			lef -= 1
		lef += 1
		if lef > 0 and p[i] - (lef - 1) < k and (p[i] - s[lef - 1] < k):
			lef = s[lef - 1]
		for j in range(lef, p[i] + 1):
			s[j] = lef
res = list()
for i in range(n):
	res.append(s[p[i]])
print(' '.join(map(str, res)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
range1 = [-1] * 256
final = [0] * n
for i in range(n):
	if range1[a[i]] == -1:
		for j in range(a[i], max(-1, a[i] - k), -1):
			if range1[j] != -1:
				if range1[j] + k > a[i]:
					range1[a[i]] = range1[j]
				else:
					range1[a[i]] = j + 1
				break
		if range1[a[i]] == -1:
			range1[a[i]] = max(0, a[i] - k + 1)
		for xx in range(range1[a[i]], a[i]):
			range1[xx] = range1[a[i]]
	final[i] = range1[a[i]]
print(*final)


def main():
	(n, k) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	solve(n, k, p)

def solve(n, k, p):
	group = 256 * [None]
	r = p[:]
	for (i, pi) in enumerate(p):
		if group[pi] is not None:
			r[i] = group[pi][0]
		else:
			lo = pi
			while lo >= 0 and pi - lo < k and (group[lo] is None):
				lo -= 1
			if lo < 0 or pi - lo == k:
				lo += 1
				hi = pi + 1
			elif pi - group[lo][0] < k:
				lo = group[lo][0]
				hi = pi + 1
			else:
				lo += 1
				hi = pi + 1
			lohi = (lo, hi)
			for j in range(lo, hi):
				group[j] = lohi
			r[i] = group[pi][0]
	print(' '.join(map(str, r)))
main()


def main():
	(n, k) = map(int, input().split())
	pixels = list(map(int, input().split()))
	colors = [-1] * 256
	colors[0] = 0
	for p in pixels:
		if colors[p] != -1:
			continue
		i = p - 1
		while i > max(0, p - k + 1) and colors[i] == -1:
			i -= 1
		g = colors[i]
		if g != -1 and g > p - k:
			for j in range(i + 1, p + 1):
				colors[j] = g
		if colors[p] == -1:
			g = max(i if colors[i] == -1 else i + 1, p - k + 1)
			for j in range(g, p + 1):
				colors[j] = g
	for p in pixels:
		print(colors[p], end=' ')
main()


(n, k) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
ans = [-1] * (max(p) + 1)
ans[0] = 0
for i in range(n):
	if ans[p[i]] < 0:
		position = p[i] - k + 1
		for j in range(max(0, p[i] - k + 1), p[i] + 1):
			if ans[j] < 0:
				position = j
				break
		j = max(0, position - 1)
		key = ans[j]
		count = 0
		while j >= 0:
			if ans[j] != key:
				position1 = j + 1
				break
			j -= 1
			count += 1
		if count + p[i] + 1 - position > k:
			key = position
		for j in range(position, p[i] + 1):
			ans[j] = key
for i in range(n):
	if i != len(p) - 1:
		wk1 = ' '
	else:
		wk1 = '\n'
	print(ans[p[i]], end=wk1)


read = lambda : map(int, input().split())
(n, k) = read()
p = list(read())
r = [-1] * 256
for i in p:
	for u in range(i, max(i - k, -1), -1):
		if r[u] >= 0:
			u += 1
			break
	if u <= i:
		if u > 0 and r[u - 1] + k > i:
			r[i] = r[u - 1]
		else:
			for j in range(u, i + 1):
				r[j] = u
	print(r[i])


import sys
read = lambda : map(int, sys.stdin.buffer.readline().split())
(n, k) = read()
p = list(read())
r = [-1] * 256
for i in p:
	for u in range(i, max(i - k, -1), -1):
		if r[u] >= 0:
			u += 1
			break
	if u <= i:
		if u > 0 and r[u - 1] + k > i:
			r[i] = r[u - 1]
		else:
			for j in range(u, i + 1):
				r[j] = u
	print(r[i])


def read():
	return [int(v) for v in input().split()]

def main():
	(n, k) = read()
	a = read()
	cache = {}
	for i in range(n):
		if a[i] not in cache:
			for v in range(1, k):
				value = a[i] - v
				if value in cache:
					if a[i] - cache[value] < k:
						cache[a[i]] = cache[value]
					else:
						cache[a[i]] = value + 1
						cache[value + 1] = value + 1
					break
			else:
				for v in range(0, k):
					cache[a[i] - v] = max(a[i] - k + 1, 0)
		print(cache[a[i]], end=' ')
main()


def main():
	(n, k) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	res = []
	group = [None] * 256
	for pi in p:
		if group[pi] is not None:
			res.append(group[pi])
			continue
		t = max(-1, pi - k)
		for i in range(pi - 1, t, -1):
			if group[i] is not None:
				if pi - group[i] < k:
					group[i + 1:pi + 1] = [group[i]] * (pi - i)
				else:
					group[i + 1:pi + 1] = [i + 1] * (pi - i)
				break
		else:
			group[t + 1:pi + 1] = [t + 1] * (pi - t)
		res.append(group[pi])
	print(' '.join((str(x) for x in res)))
main()


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
ranged = [None] * 256
check = False
check1 = False
for i in range(256):
	ranged[i] = [0, None]
result = ''
for (i, pi) in enumerate(p):
	if ranged[pi][0] == 2:
		idx = pi
		while ranged[idx][0] == 2:
			ranged[idx][0] = 1
			idx -= 1
	elif ranged[pi][0] == 0:
		idx = pi
		count = 0
		while idx > 0 and ranged[idx - 1][0] != 1 and (count < k - 1):
			idx -= 1
			count += 1
		lowest = idx
		while idx <= pi and idx < 256:
			ranged[idx][0] = 1
			ranged[idx][1] = lowest
			idx += 1
		while count < k - 1 and idx < 256 and (ranged[idx][0] != 1):
			ranged[idx][0] = 2
			ranged[idx][1] = lowest
			idx += 1
			count += 1
	result += str(ranged[pi][1]) + ' '
print(result[:-1])


def get_best_color(pixel):
	best_color = pixel - max_group_length + 1
	return best_color if best_color > 0 else 0

def get_used_color(pixel):
	best_color = get_best_color(pixel)
	for color in range(pixel, best_color - 1, -1):
		if color in colors:
			return color
	for color in range(get_best_color(best_color), best_color):
		if color in colors and colors[color] >= best_color:
			return colors[color] + 1
	return best_color
(pixels_number, max_group_length) = map(int, input().split())
pixels = map(int, input().split())
posterized_pixels = []
posterized_colors = {}
colors = {}
for pixel in pixels:
	if not pixel in posterized_colors:
		used_color = get_used_color(pixel)
		colors[used_color] = max(pixel, colors.get(used_color, -1))
		posterized_colors[pixel] = used_color
	posterized_pixels.append(posterized_colors[pixel])
print(*posterized_pixels)


(n, k) = [int(s) for s in input().split()]
p = [int(s) for s in input().split()]
map = {}
res = []
for pi in p:
	if map.get(pi) is None:
		key = pi
		for j in range(pi, pi - k, -1):
			if j < 0:
				break
			if map.get(j) is None:
				key = j
			else:
				if map[j] >= pi - k + 1:
					key = map[j]
				break
		for j in range(pi, key - 1, -1):
			if map.get(j):
				break
			map[j] = key
	res.append(map[pi])
print(*res, sep=' ')


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
cent = [1] * 256
f = [x for x in range(256)]
ans = [None] * n

def find(x):
	if f[x] == x:
		return x
	else:
		return find(f[x])

def union(x, y):
	f1 = find(x)
	f2 = find(y)
	if f1 != f2:
		f[max(f1, f2)] = min(f1, f2)
for i in range(n):
	for j in range(a[i] - 1, max(0, a[i] - k) - 1, -1):
		if cent[find(a[i])] + cent[find(j)] <= k and find(j) != find(a[i]):
			x1 = find(a[i])
			x2 = find(j)
			union(x1, x2)
			cent[find(a[i])] = cent[x1] + cent[x2]
		else:
			break
	ans[i] = find(a[i])
print(*ans)


(n, k) = map(int, input().split())
ar = [-1 for i in range(256)]
ls = list(map(int, input().split()))
for e in ls:
	if ar[e] == -1:
		tmp = max(0, e - k + 1)
		for i in range(tmp, e + 1):
			if ar[i] != -1 and ar[i] != i:
				tmp += 1
				continue
			else:
				while i <= e:
					ar[i] = tmp
					i += 1
	print(ar[e], end=' ')


def inalist(l, a):
	for i in l:
		if a in i:
			return min(i)
	return None
(n, k) = map(int, input().split())
k -= 1
a = list(map(int, input().split()))
l = list()
for i in range(n):
	found = 0
	placed = False
	ina = inalist(l, a[i])
	if ina is None:
		for j in range(a[i], max(a[i] - k - 1, -1), -1):
			inaj = inalist(l, j)
			if inaj is not None and a[i] - inaj <= k:
				l.append([ii for ii in range(inaj, a[i] + 1)])
				a[i] = inaj
				placed = True
				for kkk in range(len(l)):
					if min(l[kkk]) == inaj:
						del l[kkk]
						break
				break
			elif inaj is not None:
				found = j
				break
		if found == 0 and placed is False:
			l.append([ii for ii in range(max(a[i] - k, 0), a[i] + 1)])
			a[i] = max(a[i] - k, 0)
		if found != 0 and placed is False:
			l.append([ii for ii in range(found + 1, a[i] + 1)])
			a[i] = found + 1
	else:
		a[i] = ina
print(' '.join(list(map(str, a))))


(n, k) = map(int, input().split())
res = [-1] * 256
arr = list(map(int, input().split()))
for j in arr:
	if res[j] != -1:
		print(res[j], end=' ')
		continue
	tmp = max(0, j - k + 1)
	for i in range(tmp, j + 1):
		if res[i] != -1 and res[i] != i:
			tmp += 1
			continue
		else:
			while i <= j:
				res[i] = tmp
				i += 1
	print(res[j], end=' ')