There are $n$ students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.

The $i$-th student has integer programming skill $a_i$. All programming skills are distinct and between $1$ and $n$, inclusive.

Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and $k$ closest students to the left of him and $k$ closest students to the right of him (if there are less than $k$ students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).

Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of students and the value determining the range of chosen students during each move, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the programming skill of the $i$-th student. It is guaranteed that all programming skills are distinct.


-----Output-----

Print a string of $n$ characters; $i$-th character should be 1 if $i$-th student joins the first team, or 2 otherwise.


-----Examples-----
Input
5 2
2 4 5 3 1

Output
11111

Input
5 1
2 1 3 5 4

Output
22111

Input
7 1
7 2 1 3 5 4 6

Output
1121122

Input
5 1
2 4 5 3 1

Output
21112



-----Note-----

In the first example the first coach chooses the student on a position $3$, and the row becomes empty (all students join the first team).

In the second example the first coach chooses the student on position $4$, and the row becomes $[2, 1]$ (students with programming skills $[3, 4, 5]$ join the first team). Then the second coach chooses the student on position $1$, and the row becomes empty (and students with programming skills $[1, 2]$ join the second team).

In the third example the first coach chooses the student on position $1$, and the row becomes $[1, 3, 5, 4, 6]$ (students with programming skills $[2, 7]$ join the first team). Then the second coach chooses the student on position $5$, and the row becomes $[1, 3, 5]$ (students with programming skills $[4, 6]$ join the second team). Then the first coach chooses the student on position $3$, and the row becomes $[1]$ (students with programming skills $[3, 5]$ join the first team). And then the second coach chooses the remaining student (and the student with programming skill $1$ joins the second team).

In the fourth example the first coach chooses the student on position $3$, and the row becomes $[2, 1]$ (students with programming skills $[3, 4, 5]$ join the first team). Then the second coach chooses the student on position $1$, and the row becomes empty (and students with programming skills $[1, 2]$ join the second team).

Difficulty: introductory

Starter code:

Solutions:
IN = input
rint = lambda: int(IN())
rmint = lambda: map(int, IN().split())
rlist = lambda: list(rmint())

n, k = rmint()
pr = [i for i in range(-1, n - 1)]
nx = [i for i in range(+1, n + 1)]
ans = [0] * n
p = [0] * n
i = 0
for g in rlist():
    p[n-(g-1)-1] = i
    i += 1


def dl(x, t):
    ans[x] = t
    if nx[x] < n: pr[nx[x]] = pr[x]
    if pr[x] >= 0: nx[pr[x]] = nx[x]


t = 1
for c in p:
    #print(ans)
    #print(pr)
    #print(nx)
    if ans[c]: continue
    dl(c, t)
    j = pr[c]
    for i in range(k):
        if j < 0: break
        dl(j, t)
        j = pr[j]
    j = nx[c]
    for i in range(k):
        if j >= n: break
        dl(j, t)
        j = nx[j]
    t = 3 - t
for o in ans: print(o, end='')


n, k = map(int, input().split())

lst = map(int, input().split())

def debug():

	print('-')
	lst = [0 for _ in range(n)]
	for i in range(n):
		node = table[i]
		lst[node.index] = node.team

	print (''.join(str(x) for x in lst))
	print('-')

class Node:

	def __init__(self, index):
		self.index = index
		self.team = 0 
		self.prev = None
		self.next = None

table = [None for _ in range(n)]

prev_node = None
for index, element in enumerate(lst):

	node = Node(index)

	if prev_node:
		prev_node.next = node

	node.prev = prev_node

	table[element - 1] = node
	prev_node = node

team = 1
for i in reversed(range(n)):

	# taken
	if table[i].team != 0:
		continue

	node = table[i]
	node.team = team

	next_node = node.next
	for j in range(k):

		if next_node is None:
			break

		next_node.team = team
		next_node = next_node.next

	prev_node = node.prev
	for j in range(k):

		if prev_node is None:
			break

		prev_node.team = team
		prev_node = prev_node.prev

	if prev_node is not None:
		prev_node.next = next_node

	if next_node is not None:
		next_node.prev = prev_node

	team = 1 if team == 2 else 2

lst = [0 for _ in range(n)]
for i in range(n):
	node = table[i]
	lst[node.index] = node.team

print (''.join(str(x) for x in lst))

N, K = list(map(int, input().split()))
A = [int(a)-1 for a in input().split()]
T = [0] * N
inv = [0] * N
for i in range(N):
    inv[A[i]] = i

L = [a-1 for a in range(N)]
R = [a+1 for a in range(N)]

c = 0
t = 2
i = N-1
while c < N and i >= 0:
    j = inv[i]
    if T[j]:
        i -= 1
        continue
    t = 3 - t
    T[j] = t
    c += 1
    k = K
    pj = j
    while True:
        nj = L[pj]
        if k==0 or nj < 0:
            break
        T[nj] = t
        c += 1
        k -= 1
        pj = nj
    ll = nj
    k = K
    pj = j
    while True:
        nj = R[pj]
        if k==0 or nj >= N:
            break
        T[nj] = t
        c += 1
        k -= 1
        pj = nj
    rr = nj
    if rr < N:
        L[rr] = ll
    if ll >= 0:
        R[ll] = rr
    i -= 1

print("".join(map(str, T)))


n, k = map(int, input().split())
students = list(map(int, input().split()))
order = sorted(range(n), key=lambda x: -students[x])
neighbours = [[t - 1, t + 1] for t in range(n)]
neighbours[-1][1] = -1
turn = 0
team = [0] * n
for i in range(n):
    if team[order[i]] == 0:
        team[order[i]] = turn % 2 + 1
        left, right = neighbours[order[i]]
        for _ in range(k):
            if left != -1:
                team[left] = turn % 2 + 1
                neighbours[order[i]][0] = neighbours[left][0]
                if neighbours[left][0] != -1:
                    neighbours[neighbours[left][0]][1] = order[i]
                left = neighbours[left][0]
            if right != -1:
                team[right] = turn % 2 + 1
                neighbours[order[i]][1] = neighbours[right][1]
                if neighbours[right][1] != -1:
                    neighbours[neighbours[right][1]][0] = order[i]
                right = neighbours[right][1]
        left, right = neighbours[order[i]]
        if left != -1:
            neighbours[left][1] = right
        if right != -1:
            neighbours[right][0] = left
        turn += 1
print(*team, sep="")


import sys


ilist = [int(i) for i in input().split()]
n, k = ilist[0], ilist[1]
a = [int(i) for i in input().split()]

left, right = [], []

for i in range(n):
    left.append(i - 1)
    right.append(i + 1)

val_idx = [[a[i], i] for i in range(n)]
val_idx = sorted(val_idx, key=lambda x: x[0], reverse=True)
result = [0 for i in range(n)]

finished = 0
team = 1

for val, idx in val_idx:
    if finished == n:
        break
    
    if result[idx] != 0:
        continue
    
    result[idx] = team
    finished += 1
    left_k = k
    most_left = left[idx]

    while left_k > 0 and most_left >= 0:
        result[most_left] = team
        finished += 1
        most_left = left[most_left]
        left_k -= 1
    
    right_k = k
    most_right = right[idx]

    while right_k > 0 and most_right < n:
        result[most_right] = team
        finished += 1
        most_right = right[most_right]
        right_k -= 1
    
    if most_left >= 0:
        right[most_left] = most_right
    
    if most_right < n:
        left[most_right] = most_left
    
    if team == 1:
        team = 2
    else:
        team = 1

print(''.join([str(i) for i in result]))


class Node:
    def __init__(self, v, i):
        self.v = v
        self.i = i
        self.left = None
        self.right = None

n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
nodes = [Node(v, i) for i, v in enumerate(nums)]
sort = [[v, i] for i, v in enumerate(nums)]
sort = sorted(sort, key = lambda x: [x[0], x[1]],reverse=True)
for i in range(len(nodes)):
    if i < len(nodes) - 1:
        nodes[i].right = nodes[i + 1]
    if i > 0:
        nodes[i].left = nodes[i - 1]
ans = [0] * n

team = 1
for pair in sort:
    v, i = pair

    # if nodes[i].left == None and nodes[i].right == None:
    #     continue
    if nodes[i].i == None:
        continue
    # print(v, i)
    ans[i] = team if team == 1 else 2
    cur = nodes[i].right
    right = None
    for j in range(k):
        if cur == None:
            break
        right = cur.right
        ans[cur.i] = team if team == 1 else 2
        cur.i = None
        cur = right
    cur = nodes[i].left
    # print(cur.i, cur.v)
    left = None
    for j in range(k):
        if cur == None:
            break
        left = cur.left
        ans[cur.i] = team if team == 1 else 2
        cur.i = None
        cur = left
    # if left == None and right == None:
    #     break
    if left:
        left.right = right
    if right:
        right.left = left
    team = team ^ 1

print(''.join([str(i) for i in ans]))


n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
import sys
for i in range(n):
	l[i] -= 1
taken = [0] * n
place = [0] * n
nast = [i + 1 for i in range(n)]
poprz = [i - 1 for i in range(n)]
for i in range(n):
	place[l[i]] = i
best =  n - 1
turn = 2
while True:
	#print(taken, poprz, nast)
	#print(best)
	turn =  3 - turn
	p = place[best]
	pp = p
	#print(pp)
	taken[p] = turn
	for i in range(k):
		if nast[pp] < n:
			pp = nast[pp]
			taken[pp] = turn
		else:
			pp = n
			break
	#print('c')
	if pp < n:
		right = nast[pp]
	else:
		right = n
	pp = p
	for i in range(k):
		if poprz[pp] >= 0:
			pp = poprz[pp]
			taken[pp] = turn
		else:
			pp = -1
			break
	if pp >= 0:
		left = poprz[pp]
	else:
		left = -1
	#print(left,right)
	#print("c")
	if left > -1:
		nast[left] = right
	if right < n:
		poprz[right] = left
	while True:
		if best < 0:
			for f in taken:
				print(f, end ="")
			return
		if taken[place[best]] != 0:
			best -= 1
		else:
			break
	

n, k = map(int, input().split())
bin_ = list(map(int, input().split()))

sorted_bin = []
command = [0] * n

next_ = [i for i in range(1, n)] + [-1]
prev_ = [-1] + [i for i in range(0, n-1)]

for elem in enumerate(bin_):
    sorted_bin.append(elem)

sorted_bin.sort(key=lambda x: -x[1])

flag = 0

for ind, value in sorted_bin:
    #print(command)
    if command[ind] != 0:
        continue
    command[ind] = flag + 1
    next_i = ind
    for _ in range(k):
        next_i = next_[next_i]
        if next_i != -1:
            command[next_i] = 1 + flag
        else:
            break
    
    prev_i = ind
    for _ in range(k):
        prev_i = prev_[prev_i]
        if prev_i != -1:
            command[prev_i] = 1 + flag
        else:
            break
    
    if prev_i != -1:
        prev_i = prev_[prev_i]
    if next_i != -1:
        next_i = next_[next_i]
    if prev_i != -1:
        next_[prev_i] = next_i
    if next_i != -1:
        prev_[next_i] = prev_i
    
    flag = 1 - flag

for i in command:
    print(i, end='')

from heapq import heappop, heapify


def get_max(l, r):
    return max(a[l: r + 1])


n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

coaches = [set(), set()]

coach = 0
taken = 0

l, r = 0, 0
still_map = {0: n - 1}
done_map_l = {}
done_map_r = {}

global_map = {}
for i in range(n):
    global_map[a[i]] = i

done = [0] * (n + 1)
h = [-(i + 1) for i in range(n)]
heapify(h)
# print(a)
while taken < n:
    # max_index = -1
    # mx = -float("inf")
    # mx_l = -1
    # for l in still_map:
    #     r = still_map[l]
    #     local_max = get_max(l, r)
    #     if local_max > mx:
    #         mx = local_max
    #         mx_l = l
    local_max = -heappop(h)
    while done[local_max]:
        local_max = -heappop(h)

    max_index = global_map[local_max]

    l_search, r_search = max_index - 1, max_index + 1
    l_count, r_count = 0, 0
    l_last = max_index

    while l_search >= 0 and l_count < k:
        if l_search in done_map_r:
            new_l_search = done_map_r[l_search] - 1
            done_map_l[done_map_r[l_search]] = l_last
            done_map_r[l_last] = done_map_r[l_search]

            l_search = new_l_search
        else:
            l_count += 1
            coaches[coach].add(l_search)
            done[a[l_search]] = 1
            taken += 1
            l_search -= 1

    r_last = l_search + 1
    while r_search < n and r_count < k:
        if r_search in done_map_l:
            new_r_search = done_map_l[r_search] + 1
            done_map_r[done_map_l[r_search]] = r_last
            done_map_l[r_last] = done_map_l[r_search]

            r_search = new_r_search
        else:
            r_count += 1
            coaches[coach].add(r_search)
            done[a[r_search]] = 1
            taken += 1
            r_search += 1

    done[local_max] = 1
    coaches[coach].add(max_index)
    taken += 1
    coach ^= 1
    done_map_l[l_search + 1] = r_search - 1
    done_map_r[r_search - 1] = l_search + 1
    # print(done_map_l, done_map_r)
    # print(coaches, l_search, r_search)


print(''.join('1' if i in coaches[0] else '2' for i in range(n)))


n, k = map(int, input().split())
ls = list(map(int, input().split()))
res = {}
avail = {}
left = {}
right = {}
left[0] = -1
for i in range(1, n):
    left[i] = i-1
right[n-1] = -1
for i in range(n-1):
    right[i] = i+1
for i in range(n):
    avail[i] = True
ls = [(ls[i], i) for i in range(n)]
ls.sort(key=lambda x:x[0])
ls.reverse()
turn = 1
for i in range(n):
    if avail[ls[i][1]]==True:
        avail[ls[i][1]] = False
        cur = ls[i][1]
        res[cur] = turn
        if left[cur]!=-1:
            right[left[cur]] = right[cur]
        if right[cur]!=-1:
            left[right[cur]] = left[cur]
        for _ in range(k):
            cur = right[cur]
            if cur==-1: break
            avail[cur] = False
            res[cur] = turn
            if left[cur]!=-1:
                right[left[cur]] = right[cur]
            if right[cur]!=-1:
                left[right[cur]] = left[cur]
        cur = ls[i][1]
        for _ in range(k):
            cur = left[cur]
            if cur==-1: break
            avail[cur] = False
            res[cur] = turn
            if left[cur]!=-1:
                right[left[cur]] = right[cur]
            if right[cur]!=-1:
                left[right[cur]] = left[cur]
        if turn==1: turn = 2
        else: turn = 1
for i in range(n):
    print(res[i], end='')


n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [(a, i) for i, a in enumerate(A)]
A.sort(key=lambda x: x[0])
A.reverse()
left = [-1] * n
for i in range(1, n):
  left[i] = i - 1
right = [-1] * n
for i in range(n - 1):
  right[i] = i + 1
vis = [0] * n
join = [0] * n
jo = 1
for i in range(n):
  if not vis[A[i][1]]:
    cur = A[i][1]
    vis[cur] = 1
    join[cur] = jo
    if left[cur]!=-1:
      right[left[cur]] = right[cur]
    if right[cur]!=-1:
      left[right[cur]] = left[cur]
    # left
    for j in range(k):
      cur = left[cur]
      if cur == -1: break
      vis[cur] = 1
      join[cur] = jo
      if left[cur]!=-1:
        right[left[cur]] = right[cur]
      if right[cur]!=-1:
        left[right[cur]] = left[cur]

    # right
    cur = A[i][1]
    for j in range(k):
      cur = right[cur]
      if cur == -1: break
      vis[cur] = 1
      join[cur] = jo
      if left[cur]!=-1:
        right[left[cur]] = right[cur]
      if right[cur]!=-1:
        left[right[cur]] = left[cur]
    jo = 1 if jo == 2 else 2
print(*join, sep='')


class Node:
    def __init__(self, v, i):
        self.v = v
        self.i = i
        self.left = None
        self.right = None

n, k = map(int, input().split())
nums = list(map(int, input().split()))
nodes = [Node(v, i) for i, v in enumerate(nums)]
sort = [[v, i] for i, v in enumerate(nums)]
sort = sorted(sort, key = lambda x: [x[0], x[1]],reverse=True)
for i in range(len(nodes)):
    if i < len(nodes) - 1:
        nodes[i].right = nodes[i + 1]
    if i > 0:
        nodes[i].left = nodes[i - 1]
ans = [0] * n

team = 1
for pair in sort:
    v, i = pair

    # if nodes[i].left == None and nodes[i].right == None:
    #     continue
    if nodes[i].i == None:
        continue
    # print(v, i)
    ans[i] = team if team == 1 else 2
    cur = nodes[i].right
    right = None
    for j in range(k):
        if cur == None:
            break
        right = cur.right
        ans[cur.i] = team if team == 1 else 2
        cur.i = None
        cur = right
    cur = nodes[i].left
    # print(cur.i, cur.v)
    left = None
    for j in range(k):
        if cur == None:
            break
        left = cur.left
        ans[cur.i] = team if team == 1 else 2
        cur.i = None
        cur = left
    # if left == None and right == None:
    #     break
    if left:
        left.right = right
    if right:
        right.left = left
    team = team ^ 1

print(''.join([str(i) for i in ans]))

n,k=[int(x) for x in input().split()]
l1=[int(x)-1 for x in input().split()]
l2=[0 for x in range(0,n)]
l3=[0 for x in range(0,n)]
l4=[[] for x in range(0,n)]
#l3[i] gives index of i in input array
#l4[i][0] is prev untaken element
#l4[i][1] is forward untaken element
#l1 is input array
#l2[i] gives team of i
for i in range(0,n):
    l4[i].append(i-1)
    l4[i].append(i+1)
#print(l4)
for i in range(0,n):
    l3[l1[i]]=i
i=n-1
x=1
while(i>=0):
    t=l3[i]
    if(l2[t]!=0):
        i-=1
        continue
    else:
        l2[t]=x
        j=1
        m=l4[t][1]
        while(j<=k and m<n):
            if(l2[m]!=0): 
                if(l4[m][1]>n-1):
                    break
                m=l4[m][1]
                continue
            l2[m]=x
            if(l4[m][1]>n-1):
                    break
            m=l4[m][1]
            j+=1
        a=m
        j=1
        m=l4[t][0]
        while(j<=k and m>-1):
            if(l2[m]!=0):
                if(l4[m][0]<0):
                    break
                m=l4[m][0]
                continue
            
            l2[m]=x
            if(l4[m][0]<0):
                    break
            m=l4[m][0]
            j+=1
        b=m
        if(a<n):
            l4[a][0]=b
        if(b>-1):
            l4[b][1]=a
            
    if(x==1):
        x=2
    else:
        x=1       
    i-=1
for element in l2:
    print(element,end="")
    
    


import sys
# from sortedcontainers import SortedList
# 

from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
    from collections.abc import Sequence, MutableSequence
except ImportError:
    from collections import Sequence, MutableSequence

from functools import wraps
from sys import hexversion

if hexversion < 0x03000000:
      # pylint: disable=redefined-builtin
      # pylint: disable=redefined-builtin
    try:
        from _thread import get_ident
    except ImportError:
        from _dummy_thread import get_ident
else:
    from functools import reduce
    try:
        from _thread import get_ident
    except ImportError:
        from _dummy_thread import get_ident


def recursive_repr(fillvalue='...'):
    "Decorator to make a repr function return fillvalue for a recursive call."
    # pylint: disable=missing-docstring
    # Copied from reprlib in Python 3
    # https://hg.python.org/cpython/file/3.6/Lib/reprlib.py

    def decorating_function(user_function):
        repr_running = set()

        @wraps(user_function)
        def wrapper(self):
            key = id(self), get_ident()
            if key in repr_running:
                return fillvalue
            repr_running.add(key)
            try:
                result = user_function(self)
            finally:
                repr_running.discard(key)
            return result

        return wrapper

    return decorating_function


class SortedList(MutableSequence):
    """Sorted list is a sorted mutable sequence.

    Sorted list values are maintained in sorted order.

    Sorted list values must be comparable. The total ordering of values must
    not change while they are stored in the sorted list.

    Methods for adding values:

    * :func:`SortedList.add`
    * :func:`SortedList.update`
    * :func:`SortedList.__add__`
    * :func:`SortedList.__iadd__`
    * :func:`SortedList.__mul__`
    * :func:`SortedList.__imul__`

    Methods for removing values:

    * :func:`SortedList.clear`
    * :func:`SortedList.discard`
    * :func:`SortedList.remove`
    * :func:`SortedList.pop`
    * :func:`SortedList.__delitem__`

    Methods for looking up values:

    * :func:`SortedList.bisect_left`
    * :func:`SortedList.bisect_right`
    * :func:`SortedList.count`
    * :func:`SortedList.index`
    * :func:`SortedList.__contains__`
    * :func:`SortedList.__getitem__`

    Methods for iterating values:

    * :func:`SortedList.irange`
    * :func:`SortedList.islice`
    * :func:`SortedList.__iter__`
    * :func:`SortedList.__reversed__`

    Methods for miscellany:

    * :func:`SortedList.copy`
    * :func:`SortedList.__len__`
    * :func:`SortedList.__repr__`
    * :func:`SortedList._check`
    * :func:`SortedList._reset`

    Sorted lists use lexicographical ordering semantics when compared to other
    sequences.

    Some methods of mutable sequences are not supported and will raise
    not-implemented error.

    """
    DEFAULT_LOAD_FACTOR = 1000


    def __init__(self, iterable=None, key=None):
        """Initialize sorted list instance.

        Optional `iterable` argument provides an initial iterable of values to
        initialize the sorted list.

        Runtime complexity: `O(n*log(n))`

        >>> sl = SortedList()
        >>> sl
        SortedList([])
        >>> sl = SortedList([3, 1, 2, 5, 4])
        >>> sl
        SortedList([1, 2, 3, 4, 5])

        :param iterable: initial values (optional)

        """
        assert key is None
        self._len = 0
        self._load = self.DEFAULT_LOAD_FACTOR
        self._lists = []
        self._maxes = []
        self._index = []
        self._offset = 0

        if iterable is not None:
            self._update(iterable)


    def __new__(cls, iterable=None, key=None):
        """Create new sorted list or sorted-key list instance.

        Optional `key`-function argument will return an instance of subtype
        :class:`SortedKeyList`.

        >>> sl = SortedList()
        >>> isinstance(sl, SortedList)
        True
        >>> sl = SortedList(key=lambda x: -x)
        >>> isinstance(sl, SortedList)
        True
        >>> isinstance(sl, SortedKeyList)
        True

        :param iterable: initial values (optional)
        :param key: function used to extract comparison key (optional)
        :return: sorted list or sorted-key list instance

        """
        # pylint: disable=unused-argument
        if key is None:
            return object.__new__(cls)
        else:
            if cls is SortedList:
                return object.__new__(SortedKeyList)
            else:
                raise TypeError('inherit SortedKeyList for key argument')


    @property
    def key(self):  # pylint: disable=useless-return
        """Function used to extract comparison key from values.

        Sorted list compares values directly so the key function is none.

        """
        return None


    def _reset(self, load):
        """Reset sorted list load factor.

        The `load` specifies the load-factor of the list. The default load
        factor of 1000 works well for lists from tens to tens-of-millions of
        values. Good practice is to use a value that is the cube root of the
        list size. With billions of elements, the best load factor depends on
        your usage. It's best to leave the load factor at the default until you
        start benchmarking.

        See :doc:`implementation` and :doc:`performance-scale` for more
        information.

        Runtime complexity: `O(n)`

        :param int load: load-factor for sorted list sublists

        """
        values = reduce(iadd, self._lists, [])
        self._clear()
        self._load = load
        self._update(values)


    def clear(self):
        """Remove all values from sorted list.

        Runtime complexity: `O(n)`

        """
        self._len = 0
        del self._lists[:]
        del self._maxes[:]
        del self._index[:]
        self._offset = 0

    _clear = clear


    def add(self, value):
        """Add `value` to sorted list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList()
        >>> sl.add(3)
        >>> sl.add(1)
        >>> sl.add(2)
        >>> sl
        SortedList([1, 2, 3])

        :param value: value to add to sorted list

        """
        _lists = self._lists
        _maxes = self._maxes

        if _maxes:
            pos = bisect_right(_maxes, value)

            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)

            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)

        self._len += 1


    def _expand(self, pos):
        """Split sublists with length greater than double the load-factor.

        Updates the index when the sublist length is less than double the load
        level. This requires incrementing the nodes in a traversal from the
        leaf node to the root. For an example traversal see
        ``SortedList._loc``.

        """
        _load = self._load
        _lists = self._lists
        _index = self._index

        if len(_lists[pos]) > (_load << 1):
            _maxes = self._maxes

            _lists_pos = _lists[pos]
            half = _lists_pos[_load:]
            del _lists_pos[_load:]
            _maxes[pos] = _lists_pos[-1]

            _lists.insert(pos + 1, half)
            _maxes.insert(pos + 1, half[-1])

            del _index[:]
        else:
            if _index:
                child = self._offset + pos
                while child:
                    _index[child] += 1
                    child = (child - 1) >> 1
                _index[0] += 1


    def update(self, iterable):
        """Update sorted list by adding all values from `iterable`.

        Runtime complexity: `O(k*log(n))` -- approximate.

        >>> sl = SortedList()
        >>> sl.update([3, 1, 2])
        >>> sl
        SortedList([1, 2, 3])

        :param iterable: iterable of values to add

        """
        _lists = self._lists
        _maxes = self._maxes
        values = sorted(iterable)

        if _maxes:
            if len(values) * 4 >= self._len:
                values.extend(chain.from_iterable(_lists))
                values.sort()
                self._clear()
            else:
                _add = self.add
                for val in values:
                    _add(val)
                return

        _load = self._load
        _lists.extend(values[pos:(pos + _load)]
                      for pos in range(0, len(values), _load))
        _maxes.extend(sublist[-1] for sublist in _lists)
        self._len = len(values)
        del self._index[:]

    _update = update


    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list.

        ``sl.__contains__(value)`` <==> ``value in sl``

        Runtime complexity: `O(log(n))`

        >>> sl = SortedList([1, 2, 3, 4, 5])
        >>> 3 in sl
        True

        :param value: search for value in sorted list
        :return: true if `value` in sorted list

        """
        _maxes = self._maxes

        if not _maxes:
            return False

        pos = bisect_left(_maxes, value)

        if pos == len(_maxes):
            return False

        _lists = self._lists
        idx = bisect_left(_lists[pos], value)

        return _lists[pos][idx] == value


    def discard(self, value):
        """Remove `value` from sorted list if it is a member.

        If `value` is not a member, do nothing.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([1, 2, 3, 4, 5])
        >>> sl.discard(5)
        >>> sl.discard(0)
        >>> sl == [1, 2, 3, 4]
        True

        :param value: `value` to discard from sorted list

        """
        _maxes = self._maxes

        if not _maxes:
            return

        pos = bisect_left(_maxes, value)

        if pos == len(_maxes):
            return

        _lists = self._lists
        idx = bisect_left(_lists[pos], value)

        if _lists[pos][idx] == value:
            self._delete(pos, idx)


    def remove(self, value):
        """Remove `value` from sorted list; `value` must be a member.

        If `value` is not a member, raise ValueError.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([1, 2, 3, 4, 5])
        >>> sl.remove(5)
        >>> sl == [1, 2, 3, 4]
        True
        >>> sl.remove(0)
        Traceback (most recent call last):
          ...
        ValueError: 0 not in list

        :param value: `value` to remove from sorted list
        :raises ValueError: if `value` is not in sorted list

        """
        _maxes = self._maxes

        if not _maxes:
            raise ValueError('{0!r} not in list'.format(value))

        pos = bisect_left(_maxes, value)

        if pos == len(_maxes):
            raise ValueError('{0!r} not in list'.format(value))

        _lists = self._lists
        idx = bisect_left(_lists[pos], value)

        if _lists[pos][idx] == value:
            self._delete(pos, idx)
        else:
            raise ValueError('{0!r} not in list'.format(value))


    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`.

        Combines lists that are less than half the load level.

        Updates the index when the sublist length is more than half the load
        level. This requires decrementing the nodes in a traversal from the
        leaf node to the root. For an example traversal see
        ``SortedList._loc``.

        :param int pos: lists index
        :param int idx: sublist index

        """
        _lists = self._lists
        _maxes = self._maxes
        _index = self._index

        _lists_pos = _lists[pos]

        del _lists_pos[idx]
        self._len -= 1

        len_lists_pos = len(_lists_pos)

        if len_lists_pos > (self._load >> 1):
            _maxes[pos] = _lists_pos[-1]

            if _index:
                child = self._offset + pos
                while child > 0:
                    _index[child] -= 1
                    child = (child - 1) >> 1
                _index[0] -= 1
        elif len(_lists) > 1:
            if not pos:
                pos += 1

            prev = pos - 1
            _lists[prev].extend(_lists[pos])
            _maxes[prev] = _lists[prev][-1]

            del _lists[pos]
            del _maxes[pos]
            del _index[:]

            self._expand(prev)
        elif len_lists_pos:
            _maxes[pos] = _lists_pos[-1]
        else:
            del _lists[pos]
            del _maxes[pos]
            del _index[:]


    def _loc(self, pos, idx):
        """Convert an index pair (lists index, sublist index) into a single
        index number that corresponds to the position of the value in the
        sorted list.

        Many queries require the index be built. Details of the index are
        described in ``SortedList._build_index``.

        Indexing requires traversing the tree from a leaf node to the root. The
        parent of each node is easily computable at ``(pos - 1) // 2``.

        Left-child nodes are always at odd indices and right-child nodes are
        always at even indices.

        When traversing up from a right-child node, increment the total by the
        left-child node.

        The final index is the sum from traversal and the index in the sublist.

        For example, using the index from ``SortedList._build_index``::

            _index = 14 5 9 3 2 4 5
            _offset = 3

        Tree::

                 14
              5      9
            3   2  4   5

        Converting an index pair (2, 3) into a single index involves iterating
        like so:

        1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify
           the node as a left-child node. At such nodes, we simply traverse to
           the parent.

        2. At node 9, position 2, we recognize the node as a right-child node
           and accumulate the left-child in our total. Total is now 5 and we
           traverse to the parent at position 0.

        3. Iteration ends at the root.

        The index is then the sum of the total and sublist index: 5 + 3 = 8.

        :param int pos: lists index
        :param int idx: sublist index
        :return: index in sorted list

        """
        if not pos:
            return idx

        _index = self._index

        if not _index:
            self._build_index()

        total = 0

        # Increment pos to point in the index to len(self._lists[pos]).

        pos += self._offset

        # Iterate until reaching the root of the index tree at pos = 0.

        while pos:

            # Right-child nodes are at odd indices. At such indices
            # account the total below the left child node.

            if not pos & 1:
                total += _index[pos - 1]

            # Advance pos to the parent node.

            pos = (pos - 1) >> 1

        return total + idx


    def _pos(self, idx):
        """Convert an index into an index pair (lists index, sublist index)
        that can be used to access the corresponding lists position.

        Many queries require the index be built. Details of the index are
        described in ``SortedList._build_index``.

        Indexing requires traversing the tree to a leaf node. Each node has two
        children which are easily computable. Given an index, pos, the
        left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +
        2``.

        When the index is less than the left-child, traversal moves to the
        left sub-tree. Otherwise, the index is decremented by the left-child
        and traversal moves to the right sub-tree.

        At a child node, the indexing pair is computed from the relative
        position of the child node as compared with the offset and the remaining
        index.

        For example, using the index from ``SortedList._build_index``::

            _index = 14 5 9 3 2 4 5
            _offset = 3

        Tree::

                 14
              5      9
            3   2  4   5

        Indexing position 8 involves iterating like so:

        1. Starting at the root, position 0, 8 is compared with the left-child
           node (5) which it is greater than. When greater the index is
           decremented and the position is updated to the right child node.

        2. At node 9 with index 3, we again compare the index to the left-child
           node with value 4. Because the index is the less than the left-child
           node, we simply traverse to the left.

        3. At node 4 with index 3, we recognize that we are at a leaf node and
           stop iterating.

        4. To compute the sublist index, we subtract the offset from the index
           of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we
           simply use the index remaining from iteration. In this case, 3.

        The final index pair from our example is (2, 3) which corresponds to
        index 8 in the sorted list.

        :param int idx: index in sorted list
        :return: (lists index, sublist index) pair

        """
        if idx < 0:
            last_len = len(self._lists[-1])

            if (-idx) <= last_len:
                return len(self._lists) - 1, last_len + idx

            idx += self._len

            if idx < 0:
                raise IndexError('list index out of range')
        elif idx >= self._len:
            raise IndexError('list index out of range')

        if idx < len(self._lists[0]):
            return 0, idx

        _index = self._index

        if not _index:
            self._build_index()

        pos = 0
        child = 1
        len_index = len(_index)

        while child < len_index:
            index_child = _index[child]

            if idx < index_child:
                pos = child
            else:
                idx -= index_child
                pos = child + 1

            child = (pos << 1) + 1

        return (pos - self._offset, idx)


    def _build_index(self):
        """Build a positional index for indexing the sorted list.

        Indexes are represented as binary trees in a dense array notation
        similar to a binary heap.

        For example, given a lists representation storing integers::

            0: [1, 2, 3]
            1: [4, 5]
            2: [6, 7, 8, 9]
            3: [10, 11, 12, 13, 14]

        The first transformation maps the sub-lists by their length. The
        first row of the index is the length of the sub-lists::

            0: [3, 2, 4, 5]

        Each row after that is the sum of consecutive pairs of the previous
        row::

            1: [5, 9]
            2: [14]

        Finally, the index is built by concatenating these lists together::

            _index = [14, 5, 9, 3, 2, 4, 5]

        An offset storing the start of the first row is also stored::

            _offset = 3

        When built, the index can be used for efficient indexing into the list.
        See the comment and notes on ``SortedList._pos`` for details.

        """
        row0 = list(map(len, self._lists))

        if len(row0) == 1:
            self._index[:] = row0
            self._offset = 0
            return

        head = iter(row0)
        tail = iter(head)
        row1 = list(starmap(add, list(zip(head, tail))))

        if len(row0) & 1:
            row1.append(row0[-1])

        if len(row1) == 1:
            self._index[:] = row1 + row0
            self._offset = 1
            return

        size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
        row1.extend(repeat(0, size - len(row1)))
        tree = [row0, row1]

        while len(tree[-1]) > 1:
            head = iter(tree[-1])
            tail = iter(head)
            row = list(starmap(add, list(zip(head, tail))))
            tree.append(row)

        reduce(iadd, reversed(tree), self._index)
        self._offset = size * 2 - 1


    def __delitem__(self, index):
        """Remove value at `index` from sorted list.

        ``sl.__delitem__(index)`` <==> ``del sl[index]``

        Supports slicing.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList('abcde')
        >>> del sl[2]
        >>> sl
        SortedList(['a', 'b', 'd', 'e'])
        >>> del sl[:2]
        >>> sl
        SortedList(['d', 'e'])

        :param index: integer or slice for indexing
        :raises IndexError: if index out of range

        """
        if isinstance(index, slice):
            start, stop, step = index.indices(self._len)

            if step == 1 and start < stop:
                if start == 0 and stop == self._len:
                    return self._clear()
                elif self._len <= 8 * (stop - start):
                    values = self._getitem(slice(None, start))
                    if stop < self._len:
                        values += self._getitem(slice(stop, None))
                    self._clear()
                    return self._update(values)

            indices = list(range(start, stop, step))

            # Delete items from greatest index to least so
            # that the indices remain valid throughout iteration.

            if step > 0:
                indices = reversed(indices)

            _pos, _delete = self._pos, self._delete

            for index in indices:
                pos, idx = _pos(index)
                _delete(pos, idx)
        else:
            pos, idx = self._pos(index)
            self._delete(pos, idx)


    def __getitem__(self, index):
        """Lookup value at `index` in sorted list.

        ``sl.__getitem__(index)`` <==> ``sl[index]``

        Supports slicing.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList('abcde')
        >>> sl[1]
        'b'
        >>> sl[-1]
        'e'
        >>> sl[2:5]
        ['c', 'd', 'e']

        :param index: integer or slice for indexing
        :return: value or list of values
        :raises IndexError: if index out of range

        """
        _lists = self._lists

        if isinstance(index, slice):
            start, stop, step = index.indices(self._len)

            if step == 1 and start < stop:
                if start == 0 and stop == self._len:
                    return reduce(iadd, self._lists, [])

                start_pos, start_idx = self._pos(start)

                if stop == self._len:
                    stop_pos = len(_lists) - 1
                    stop_idx = len(_lists[stop_pos])
                else:
                    stop_pos, stop_idx = self._pos(stop)

                if start_pos == stop_pos:
                    return _lists[start_pos][start_idx:stop_idx]

                prefix = _lists[start_pos][start_idx:]
                middle = _lists[(start_pos + 1):stop_pos]
                result = reduce(iadd, middle, prefix)
                result += _lists[stop_pos][:stop_idx]

                return result

            if step == -1 and start > stop:
                result = self._getitem(slice(stop + 1, start + 1))
                result.reverse()
                return result

            # Return a list because a negative step could
            # reverse the order of the items and this could
            # be the desired behavior.

            indices = list(range(start, stop, step))
            return list(self._getitem(index) for index in indices)
        else:
            if self._len:
                if index == 0:
                    return _lists[0][0]
                elif index == -1:
                    return _lists[-1][-1]
            else:
                raise IndexError('list index out of range')

            if 0 <= index < len(_lists[0]):
                return _lists[0][index]

            len_last = len(_lists[-1])

            if -len_last < index < 0:
                return _lists[-1][len_last + index]

            pos, idx = self._pos(index)
            return _lists[pos][idx]

    _getitem = __getitem__


    def __setitem__(self, index, value):
        """Raise not-implemented error.

        ``sl.__setitem__(index, value)`` <==> ``sl[index] = value``

        :raises NotImplementedError: use ``del sl[index]`` and
            ``sl.add(value)`` instead

        """
        message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
        raise NotImplementedError(message)


    def __iter__(self):
        """Return an iterator over the sorted list.

        ``sl.__iter__()`` <==> ``iter(sl)``

        Iterating the sorted list while adding or deleting values may raise a
        :exc:`RuntimeError` or fail to iterate over all values.

        """
        return chain.from_iterable(self._lists)


    def __reversed__(self):
        """Return a reverse iterator over the sorted list.

        ``sl.__reversed__()`` <==> ``reversed(sl)``

        Iterating the sorted list while adding or deleting values may raise a
        :exc:`RuntimeError` or fail to iterate over all values.

        """
        return chain.from_iterable(list(map(reversed, reversed(self._lists))))


    def reverse(self):
        """Raise not-implemented error.

        Sorted list maintains values in ascending sort order. Values may not be
        reversed in-place.

        Use ``reversed(sl)`` for an iterator over values in descending sort
        order.

        Implemented to override `MutableSequence.reverse` which provides an
        erroneous default implementation.

        :raises NotImplementedError: use ``reversed(sl)`` instead

        """
        raise NotImplementedError('use ``reversed(sl)`` instead')


    def islice(self, start=None, stop=None, reverse=False):
        """Return an iterator that slices sorted list from `start` to `stop`.

        The `start` and `stop` index are treated inclusive and exclusive,
        respectively.

        Both `start` and `stop` default to `None` which is automatically
        inclusive of the beginning and end of the sorted list.

        When `reverse` is `True` the values are yielded from the iterator in
        reverse order; `reverse` defaults to `False`.

        >>> sl = SortedList('abcdefghij')
        >>> it = sl.islice(2, 6)
        >>> list(it)
        ['c', 'd', 'e', 'f']

        :param int start: start index (inclusive)
        :param int stop: stop index (exclusive)
        :param bool reverse: yield values in reverse order
        :return: iterator

        """
        _len = self._len

        if not _len:
            return iter(())

        start, stop, _ = slice(start, stop).indices(self._len)

        if start >= stop:
            return iter(())

        _pos = self._pos

        min_pos, min_idx = _pos(start)

        if stop == _len:
            max_pos = len(self._lists) - 1
            max_idx = len(self._lists[-1])
        else:
            max_pos, max_idx = _pos(stop)

        return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)


    def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
        """Return an iterator that slices sorted list using two index pairs.

        The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
        first inclusive and the latter exclusive. See `_pos` for details on how
        an index is converted to an index pair.

        When `reverse` is `True`, values are yielded from the iterator in
        reverse order.

        """
        _lists = self._lists

        if min_pos > max_pos:
            return iter(())

        if min_pos == max_pos:
            if reverse:
                indices = reversed(list(range(min_idx, max_idx)))
                return list(map(_lists[min_pos].__getitem__, indices))

            indices = list(range(min_idx, max_idx))
            return list(map(_lists[min_pos].__getitem__, indices))

        next_pos = min_pos + 1

        if next_pos == max_pos:
            if reverse:
                min_indices = list(range(min_idx, len(_lists[min_pos])))
                max_indices = list(range(max_idx))
                return chain(
                    list(map(_lists[max_pos].__getitem__, reversed(max_indices))),
                    list(map(_lists[min_pos].__getitem__, reversed(min_indices))),
                )

            min_indices = list(range(min_idx, len(_lists[min_pos])))
            max_indices = list(range(max_idx))
            return chain(
                list(map(_lists[min_pos].__getitem__, min_indices)),
                list(map(_lists[max_pos].__getitem__, max_indices)),
            )

        if reverse:
            min_indices = list(range(min_idx, len(_lists[min_pos])))
            sublist_indices = list(range(next_pos, max_pos))
            sublists = list(map(_lists.__getitem__, reversed(sublist_indices)))
            max_indices = list(range(max_idx))
            return chain(
                list(map(_lists[max_pos].__getitem__, reversed(max_indices))),
                chain.from_iterable(list(map(reversed, sublists))),
                list(map(_lists[min_pos].__getitem__, reversed(min_indices))),
            )

        min_indices = list(range(min_idx, len(_lists[min_pos])))
        sublist_indices = list(range(next_pos, max_pos))
        sublists = list(map(_lists.__getitem__, sublist_indices))
        max_indices = list(range(max_idx))
        return chain(
            list(map(_lists[min_pos].__getitem__, min_indices)),
            chain.from_iterable(sublists),
            list(map(_lists[max_pos].__getitem__, max_indices)),
        )


    def irange(self, minimum=None, maximum=None, inclusive=(True, True),
               reverse=False):
        """Create an iterator of values between `minimum` and `maximum`.

        Both `minimum` and `maximum` default to `None` which is automatically
        inclusive of the beginning and end of the sorted list.

        The argument `inclusive` is a pair of booleans that indicates whether
        the minimum and maximum ought to be included in the range,
        respectively. The default is ``(True, True)`` such that the range is
        inclusive of both minimum and maximum.

        When `reverse` is `True` the values are yielded from the iterator in
        reverse order; `reverse` defaults to `False`.

        >>> sl = SortedList('abcdefghij')
        >>> it = sl.irange('c', 'f')
        >>> list(it)
        ['c', 'd', 'e', 'f']

        :param minimum: minimum value to start iterating
        :param maximum: maximum value to stop iterating
        :param inclusive: pair of booleans
        :param bool reverse: yield values in reverse order
        :return: iterator

        """
        _maxes = self._maxes

        if not _maxes:
            return iter(())

        _lists = self._lists

        # Calculate the minimum (pos, idx) pair. By default this location
        # will be inclusive in our calculation.

        if minimum is None:
            min_pos = 0
            min_idx = 0
        else:
            if inclusive[0]:
                min_pos = bisect_left(_maxes, minimum)

                if min_pos == len(_maxes):
                    return iter(())

                min_idx = bisect_left(_lists[min_pos], minimum)
            else:
                min_pos = bisect_right(_maxes, minimum)

                if min_pos == len(_maxes):
                    return iter(())

                min_idx = bisect_right(_lists[min_pos], minimum)

        # Calculate the maximum (pos, idx) pair. By default this location
        # will be exclusive in our calculation.

        if maximum is None:
            max_pos = len(_maxes) - 1
            max_idx = len(_lists[max_pos])
        else:
            if inclusive[1]:
                max_pos = bisect_right(_maxes, maximum)

                if max_pos == len(_maxes):
                    max_pos -= 1
                    max_idx = len(_lists[max_pos])
                else:
                    max_idx = bisect_right(_lists[max_pos], maximum)
            else:
                max_pos = bisect_left(_maxes, maximum)

                if max_pos == len(_maxes):
                    max_pos -= 1
                    max_idx = len(_lists[max_pos])
                else:
                    max_idx = bisect_left(_lists[max_pos], maximum)

        return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)


    def __len__(self):
        """Return the size of the sorted list.

        ``sl.__len__()`` <==> ``len(sl)``

        :return: size of sorted list

        """
        return self._len


    def bisect_left(self, value):
        """Return an index to insert `value` in the sorted list.

        If the `value` is already present, the insertion point will be before
        (to the left of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([10, 11, 12, 13, 14])
        >>> sl.bisect_left(12)
        2

        :param value: insertion index of value in sorted list
        :return: index

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos = bisect_left(_maxes, value)

        if pos == len(_maxes):
            return self._len

        idx = bisect_left(self._lists[pos], value)
        return self._loc(pos, idx)


    def bisect_right(self, value):
        """Return an index to insert `value` in the sorted list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([10, 11, 12, 13, 14])
        >>> sl.bisect_right(12)
        3

        :param value: insertion index of value in sorted list
        :return: index

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos = bisect_right(_maxes, value)

        if pos == len(_maxes):
            return self._len

        idx = bisect_right(self._lists[pos], value)
        return self._loc(pos, idx)

    bisect = bisect_right
    _bisect_right = bisect_right


    def count(self, value):
        """Return number of occurrences of `value` in the sorted list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
        >>> sl.count(3)
        3

        :param value: value to count in sorted list
        :return: count

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos_left = bisect_left(_maxes, value)

        if pos_left == len(_maxes):
            return 0

        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        pos_right = bisect_right(_maxes, value)

        if pos_right == len(_maxes):
            return self._len - self._loc(pos_left, idx_left)

        idx_right = bisect_right(_lists[pos_right], value)

        if pos_left == pos_right:
            return idx_right - idx_left

        right = self._loc(pos_right, idx_right)
        left = self._loc(pos_left, idx_left)
        return right - left


    def copy(self):
        """Return a shallow copy of the sorted list.

        Runtime complexity: `O(n)`

        :return: new sorted list

        """
        return self.__class__(self)

    __copy__ = copy


    def append(self, value):
        """Raise not-implemented error.

        Implemented to override `MutableSequence.append` which provides an
        erroneous default implementation.

        :raises NotImplementedError: use ``sl.add(value)`` instead

        """
        raise NotImplementedError('use ``sl.add(value)`` instead')


    def extend(self, values):
        """Raise not-implemented error.

        Implemented to override `MutableSequence.extend` which provides an
        erroneous default implementation.

        :raises NotImplementedError: use ``sl.update(values)`` instead

        """
        raise NotImplementedError('use ``sl.update(values)`` instead')


    def insert(self, index, value):
        """Raise not-implemented error.

        :raises NotImplementedError: use ``sl.add(value)`` instead

        """
        raise NotImplementedError('use ``sl.add(value)`` instead')


    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list.

        Raise :exc:`IndexError` if the sorted list is empty or index is out of
        range.

        Negative indices are supported.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList('abcde')
        >>> sl.pop()
        'e'
        >>> sl.pop(2)
        'c'
        >>> sl
        SortedList(['a', 'b', 'd'])

        :param int index: index of value (default -1)
        :return: value
        :raises IndexError: if index is out of range

        """
        if not self._len:
            raise IndexError('pop index out of range')

        _lists = self._lists

        if index == 0:
            val = _lists[0][0]
            self._delete(0, 0)
            return val

        if index == -1:
            pos = len(_lists) - 1
            loc = len(_lists[pos]) - 1
            val = _lists[pos][loc]
            self._delete(pos, loc)
            return val

        if 0 <= index < len(_lists[0]):
            val = _lists[0][index]
            self._delete(0, index)
            return val

        len_last = len(_lists[-1])

        if -len_last < index < 0:
            pos = len(_lists) - 1
            loc = len_last + index
            val = _lists[pos][loc]
            self._delete(pos, loc)
            return val

        pos, idx = self._pos(index)
        val = _lists[pos][idx]
        self._delete(pos, idx)
        return val


    def index(self, value, start=None, stop=None):
        """Return first index of value in sorted list.

        Raise ValueError if `value` is not present.

        Index must be between `start` and `stop` for the `value` to be
        considered present. The default value, None, for `start` and `stop`
        indicate the beginning and end of the sorted list.

        Negative indices are supported.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList('abcde')
        >>> sl.index('d')
        3
        >>> sl.index('z')
        Traceback (most recent call last):
          ...
        ValueError: 'z' is not in list

        :param value: value in sorted list
        :param int start: start index (default None, start of sorted list)
        :param int stop: stop index (default None, end of sorted list)
        :return: index of value
        :raises ValueError: if value is not present

        """
        _len = self._len

        if not _len:
            raise ValueError('{0!r} is not in list'.format(value))

        if start is None:
            start = 0
        if start < 0:
            start += _len
        if start < 0:
            start = 0

        if stop is None:
            stop = _len
        if stop < 0:
            stop += _len
        if stop > _len:
            stop = _len

        if stop <= start:
            raise ValueError('{0!r} is not in list'.format(value))

        _maxes = self._maxes
        pos_left = bisect_left(_maxes, value)

        if pos_left == len(_maxes):
            raise ValueError('{0!r} is not in list'.format(value))

        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)

        if _lists[pos_left][idx_left] != value:
            raise ValueError('{0!r} is not in list'.format(value))

        stop -= 1
        left = self._loc(pos_left, idx_left)

        if start <= left:
            if left <= stop:
                return left
        else:
            right = self._bisect_right(value) - 1

            if start <= right:
                return start

        raise ValueError('{0!r} is not in list'.format(value))


    def __add__(self, other):
        """Return new sorted list containing all values in both sequences.

        ``sl.__add__(other)`` <==> ``sl + other``

        Values in `other` do not need to be in sorted order.

        Runtime complexity: `O(n*log(n))`

        >>> sl1 = SortedList('bat')
        >>> sl2 = SortedList('cat')
        >>> sl1 + sl2
        SortedList(['a', 'a', 'b', 'c', 't', 't'])

        :param other: other iterable
        :return: new sorted list

        """
        values = reduce(iadd, self._lists, [])
        values.extend(other)
        return self.__class__(values)

    __radd__ = __add__


    def __iadd__(self, other):
        """Update sorted list with values from `other`.

        ``sl.__iadd__(other)`` <==> ``sl += other``

        Values in `other` do not need to be in sorted order.

        Runtime complexity: `O(k*log(n))` -- approximate.

        >>> sl = SortedList('bat')
        >>> sl += 'cat'
        >>> sl
        SortedList(['a', 'a', 'b', 'c', 't', 't'])

        :param other: other iterable
        :return: existing sorted list

        """
        self._update(other)
        return self


    def __mul__(self, num):
        """Return new sorted list with `num` shallow copies of values.

        ``sl.__mul__(num)`` <==> ``sl * num``

        Runtime complexity: `O(n*log(n))`

        >>> sl = SortedList('abc')
        >>> sl * 3
        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])

        :param int num: count of shallow copies
        :return: new sorted list

        """
        values = reduce(iadd, self._lists, []) * num
        return self.__class__(values)

    __rmul__ = __mul__


    def __imul__(self, num):
        """Update the sorted list with `num` shallow copies of values.

        ``sl.__imul__(num)`` <==> ``sl *= num``

        Runtime complexity: `O(n*log(n))`

        >>> sl = SortedList('abc')
        >>> sl *= 3
        >>> sl
        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])

        :param int num: count of shallow copies
        :return: existing sorted list

        """
        values = reduce(iadd, self._lists, []) * num
        self._clear()
        self._update(values)
        return self


    def __make_cmp(seq_op, symbol, doc):
        "Make comparator method."
        def comparer(self, other):
            "Compare method for sorted list and sequence."
            if not isinstance(other, Sequence):
                return NotImplemented

            self_len = self._len
            len_other = len(other)

            if self_len != len_other:
                if seq_op is eq:
                    return False
                if seq_op is ne:
                    return True

            for alpha, beta in zip(self, other):
                if alpha != beta:
                    return seq_op(alpha, beta)

            return seq_op(self_len, len_other)

        seq_op_name = seq_op.__name__
        comparer.__name__ = '__{0}__'.format(seq_op_name)
        doc_str = """Return true if and only if sorted list is {0} `other`.

        ``sl.__{1}__(other)`` <==> ``sl {2} other``

        Comparisons use lexicographical order as with sequences.

        Runtime complexity: `O(n)`

        :param other: `other` sequence
        :return: true if sorted list is {0} `other`

        """
        comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
        return comparer


    __eq__ = __make_cmp(eq, '==', 'equal to')
    __ne__ = __make_cmp(ne, '!=', 'not equal to')
    __lt__ = __make_cmp(lt, '<', 'less than')
    __gt__ = __make_cmp(gt, '>', 'greater than')
    __le__ = __make_cmp(le, '<=', 'less than or equal to')
    __ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
    __make_cmp = staticmethod(__make_cmp)


    @recursive_repr()
    def __repr__(self):
        """Return string representation of sorted list.

        ``sl.__repr__()`` <==> ``repr(sl)``

        :return: string representation

        """
        return '{0}({1!r})'.format(type(self).__name__, list(self))


    def _check(self):
        """Check invariants of sorted list.

        Runtime complexity: `O(n)`

        """
        try:
            assert self._load >= 4
            assert len(self._maxes) == len(self._lists)
            assert self._len == sum(len(sublist) for sublist in self._lists)

            # Check all sublists are sorted.

            for sublist in self._lists:
                for pos in range(1, len(sublist)):
                    assert sublist[pos - 1] <= sublist[pos]

            # Check beginning/end of sublists are sorted.

            for pos in range(1, len(self._lists)):
                assert self._lists[pos - 1][-1] <= self._lists[pos][0]

            # Check _maxes index is the last value of each sublist.

            for pos in range(len(self._maxes)):
                assert self._maxes[pos] == self._lists[pos][-1]

            # Check sublist lengths are less than double load-factor.

            double = self._load << 1
            assert all(len(sublist) <= double for sublist in self._lists)

            # Check sublist lengths are greater than half load-factor for all
            # but the last sublist.

            half = self._load >> 1
            for pos in range(0, len(self._lists) - 1):
                assert len(self._lists[pos]) >= half

            if self._index:
                assert self._len == self._index[0]
                assert len(self._index) == self._offset + len(self._lists)

                # Check index leaf nodes equal length of sublists.

                for pos in range(len(self._lists)):
                    leaf = self._index[self._offset + pos]
                    assert leaf == len(self._lists[pos])

                # Check index branch nodes are the sum of their children.

                for pos in range(self._offset):
                    child = (pos << 1) + 1
                    if child >= len(self._index):
                        assert self._index[pos] == 0
                    elif child + 1 == len(self._index):
                        assert self._index[pos] == self._index[child]
                    else:
                        child_sum = self._index[child] + self._index[child + 1]
                        assert child_sum == self._index[pos]
        except:
            import sys
            import traceback
            traceback.print_exc(file=sys.stdout)
            print('len', self._len)
            print('load', self._load)
            print('offset', self._offset)
            print('len_index', len(self._index))
            print('index', self._index)
            print('len_maxes', len(self._maxes))
            print('maxes', self._maxes)
            print('len_lists', len(self._lists))
            print('lists', self._lists)
            raise


fin = sys.stdin.readline
n, k = [int(elem) for elem in fin().split()]
a_list = sorted([(int(elem), i) for i, elem in enumerate(fin().split())], reverse=True)
# print(a_list)

idx_to_team = [0] * n
programmers_in_row = SortedList(list(range(n)))
coach = 1
for a, i in a_list:
    if idx_to_team[i] != 0:
        continue

    # Add them to the team
    cur_idx = programmers_in_row.bisect_left(i)
    cur_added = []
    for j in range(max(0, cur_idx - k), min(len(programmers_in_row), cur_idx + k + 1)):
        neighbor = programmers_in_row[j]
        idx_to_team[neighbor] = coach
        cur_added.append(neighbor)

    # Discard them from the row
    for added_programmer in cur_added:
        programmers_in_row.remove(added_programmer)

    coach = 2 if coach == 1 else 1


print("".join(str(coach) for coach in idx_to_team))


import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))

A_INV=[-1]*n
for i in range(n):
    A_INV[A[i]-1]=i
    
L=list(range(-1,n-1))
R=list(range(1,n+1))

USELIST=[0]*n
ANS=[0]*n
NOW=1

for a in A_INV[::-1]:
    if USELIST[a]==1:
        continue
    USELIST[a]=1
    ANS[a]=NOW

    if 0<=a<n and 0<=L[a]<n:
        R[L[a]]=R[a]

    if 0<=a<n and 0<=R[a]<n:
        L[R[a]]=L[a]

    r=a
    for step in range(k):
        r=R[r]
        if r<0 or r>=n:
            break
        ANS[r]=NOW
        USELIST[r]=1

        if 0<=r<n and 0<=L[r]<n:
            R[L[r]]=R[r]

        if 0<=r<n and 0<=R[r]<n:
            L[R[r]]=L[r]

    l=a
    for step in range(k):
        l=L[l]
        if l<0 or l>=n:
            break
        ANS[l]=NOW
        USELIST[l]=1

        if 0<=l<n and 0<=L[l]<n:
            R[L[l]]=R[l]

        if 0<=l<n and 0<=R[l]<n:
            L[R[l]]=L[l]

    NOW=3-NOW
    #print(*ANS,USELIST,L,R)

print("".join(map(str,ANS)))
        
        


import heapq


n, k = [int(i) for i in input().split(' ')]

stus = [int(i) for i in input().split(' ')]
ss = sorted(list(enumerate(stus)), key=lambda x: -x[1])
nb = [[i - 1, i + 1] for i in range(n)]
ssid = 0

res = [-1] * n
turn = 0
count = 0
for idx, val in ss:
    if res[idx] != -1:
        continue
    res[idx] = turn % 2 + 1
    left, right = nb[idx]
    for i in range(k):
        if right < n and res[right] == -1:
            res[right] = turn % 2 + 1
            nb[idx][1] = nb[right][1]
            right = nb[right][1]

        if left >= 0 and res[left] == -1:
            res[left] = turn % 2 + 1
            nb[idx][0] = nb[left][0]
            left = nb[left][0]
        if nb[idx][1] < n:
            nb[nb[idx][1]][0] = nb[idx][0]
        if nb[idx][0] >= 0:
            nb[nb[idx][0]][1] = nb[idx][1]
    turn += 1
print(''.join([str(i) for i in res]))


# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = sys.stdin.readline().split()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        k = self.next_int()
        x = [self.next_int() for _ in range(0, n)]
        bf = [x - 1 for x in range(0, n)]
        nx = [x + 1 for x in range(0, n)]
        t = [0 for _ in range(0, n)]
        od = [0 for _ in range(0, n)]
        for i in range(0, n):
            od[x[i] - 1] = i
        tt = 1
        for i in range(n - 1, -1, -1):
            if t[od[i]] == 0:
                o = od[i]
                t[o] = tt
                for _ in range(0, k):
                    o = bf[o]
                    if o == -1:
                        break
                    t[o] = tt

                oo = od[i]
                for _ in range(0, k):
                    oo = nx[oo]
                    if oo == n:
                        break
                    t[oo] = tt
                if o != -1 and bf[o] != -1:
                    nx[bf[o]] = oo if oo == n else nx[oo]
                if oo != n and nx[oo] != n:
                    bf[nx[oo]] = o if o == -1 else bf[o]
                tt = 3 - tt
        print(''.join([str(xx) for xx in t]))


def __starting_point():
    Main().solve()

__starting_point()

import heapq

n, k = map(int, input().split())
a = list(map(int, input().split()))

first = [False] * n
second = [False] * n
pq = []
nexts = [None] * n
prevs = [None] * n
for i in range(n):
    heapq.heappush(pq, (-a[i], i))
    if i < n - 1:
        nexts[i] = i + 1
    if i > 0:
        prevs[i] = i - 1

turn = 0
while pq:
    _, curIdx = heapq.heappop(pq)
    if first[curIdx] or second[curIdx]:
        continue
    if turn == 0:
        first[curIdx] = True
    else:
        second[curIdx] = True

    fromLeft = 0
    i = prevs[curIdx]
    while fromLeft < k and i != None:
        if turn == 0:
            first[i] = True
        else:
            second[i] = True
        i = prevs[i]
        fromLeft += 1
    prevs[curIdx] = i

    fromRight = 0
    i = nexts[curIdx]
    while fromRight < k and i != None:
        if turn == 0:
            first[i] = True
        else:
            second[i] = True
        i = nexts[i]
        fromRight += 1
    nexts[curIdx] = i

    if prevs[curIdx] != None:
        nexts[prevs[curIdx]] = nexts[curIdx]
    if nexts[curIdx] != None:
        prevs[nexts[curIdx]] = prevs[curIdx]

    turn ^= 1

for i in range(n):
    print(1 if first[i] else 2, end='')

n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
pos = {}
pre = [i-1 for i in range(n+2)]
nex = [i+1 for i in range(n+2)]
for i,j in enumerate(a):
    pos[j] = i+1
group = 1
taken = [0 for _ in range(n+2)]
right = left = 0
for i in range(n,0,-1):
    if taken[pos[i]] != 0:
        continue
    group = (group + 1) % 2
    p = k
    now = pos[i]
    taken[now] = group + 1
    while p > 0 and now <= n:
        now = nex[now]
        if taken[now] == 0:
            taken[now] = group + 1
            p -= 1
        right = now
    p = k
    now = pos[i]
    while p > 0 and now > 0:
        now = pre[now]
        if taken[now] == 0:
            taken[now] = group + 1
            p -= 1
        left = now
    nex[left] = right
    pre[right] = left
ans = [str(i) for i in taken]
print(''.join(ans[1:n+1]))


import heapq
def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))

    q = []
    for i in range(n):
        heapq.heappush(q, (-a[i], i))

    teams = [0] * n
    nextLeft = [i-1 for i in range(n)]
    nextRight = [i+1 for i in range(n)]
    used = [False] * n

    team = 0
    while q:
        item, pos = heapq.heappop(q)
        while q and used[pos]:
            item, pos = heapq.heappop(q)
        if used[pos]:
            break  # all done

        teams[pos] = team + 1
        used[pos] = True

        deletedLeft = 0
        currLeft = pos
        while deletedLeft < k and nextLeft[currLeft] >= 0:
            currLeft = nextLeft[currLeft]
            used[currLeft] = True
            teams[currLeft] = team + 1
            deletedLeft += 1

        deletedRight = 0
        currRight = pos
        while deletedRight < k and nextRight[currRight] < n:
            currRight = nextRight[currRight]
            used[currRight] = True
            teams[currRight] = team + 1
            deletedRight += 1

        if currLeft >= 0:
            currLeft = nextLeft[currLeft]
        if currRight < n:
            currRight = nextRight[currRight]

        if currLeft >= 0:
            nextRight[currLeft] = currRight
        if currRight < n:
            nextLeft[currRight] = currLeft

        team = (team + 1) % 2

    print(''.join(map(str, teams)))


def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
row = list(map(int, input().split()))

ranked = list([x[1] for x in sorted([(-x[1], x[0]) for x in enumerate(row)])])

prev = list(range(-1, n - 1))
nxt = list(range(1, n + 1))
teams = [0] * n
current = 1
total = 0

for i in ranked:
    if total > n:
        break

    if not teams[i]:
        teams[i] = current
        took = 1

        # walk left
        count = k
        left = prev[i]
        while count > 0 and left != -1:
            teams[left] = current
            left = prev[left]
            took += 1
            count -= 1

        # walk right
        count = k
        right = nxt[i]
        while count > 0 and right != n:
            teams[right] = current
            right = nxt[right]
            took += 1
            count -= 1

        if left != -1:
            nxt[left] = right

        if right != n:
            prev[right] = left

        total += took
        current = 2 if current == 1 else 1

print(''.join(map(str, teams)))


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
pre = {}
nex = {}
d = {}
for i in range(n):
    d[a[i]] = i
for i in range(n):
    pre[i] = i - 1
    nex[i] = i + 1

t = 1
ans = [-1] * n
for i in range(n, 0, -1):
    j = d[i]
    if ans[j] != -1:
        continue
    ans[j] = t
    l, r = pre[j], nex[j]
    for p in range(k):
        if l == -1:
            break
        ans[l] = t
        l = pre[l]

    for p in range(k):
        if r == n:
            break
        ans[r] = t
        r = nex[r]

    if l >= 0:
        nex[l] = r
    if r < n:
        pre[r] = l

    t = 3 - t

print(''.join(map(str, ans)))



#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #552 (Div. 3)

Problem E. Two Teams

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '1.0'
__date__ = '2019-04-17'

import sys


def remove_me(to_left, to_right, index):
    left_id = to_left[index]
    right_id = to_right[index]
    if right_id < len(to_left):
        to_left[right_id] = left_id
    if left_id >= 0:
        to_right[left_id] = right_id
    return (left_id, right_id)

def join_team(n, k, students):
    teams = ['0'] * n
    mydict = dict(list(zip(students, list(range(n)))))    # {skill: id}
    to_left = [i-1 for i in range(n)]
    to_right = [i+1 for i in range(n)]

    next_chosen = n
    chosen_total = 0
    while chosen_total < n:
        for couch in ['1', '2']:
            while teams[mydict[next_chosen]] != '0':
                next_chosen -= 1
                if next_chosen < 1:
                    return teams
            teams[mydict[next_chosen]] = couch
            chosen_total += 1
            left_id, right_id = remove_me(to_left, to_right,
                                          mydict[next_chosen])
            for i in range(k):
                if left_id < 0:
                    break
                teams[left_id] = couch
                chosen_total += 1
                left_id, right_id = remove_me(to_left, to_right, left_id)
            for i in range(k):
                if right_id >= n:
                    break
                teams[right_id] = couch
                chosen_total += 1
                left_id, right_id = remove_me(to_left, to_right, right_id)
    return teams

def main(argv=None):
    n, k = list(map(int, input().split()))
    students = list(map(int, input().split()))
    print(''.join(join_team(n, k, students)))
    return 0

def __starting_point():
    STATUS = main()
    return(STATUS)


__starting_point()