A despotic king decided that his kingdom needed to be rid of corruption and disparity. He called his prime minister and ordered that all corrupt citizens be put to death. Moreover, he wanted this done quickly.
The wily prime minister realised that investigating every citizen to decide who was corrupt and who was not was rather difficult. So he decided on the following plan: He ordered all the citizens to appear in the court one by one and declare their wealth.
The king does not sit in the court all the time (he has other important business to attend to - for instance, meet dignitaries from neighbouring kingdoms, spend time with his family …) Whenever the king walks into the court, the prime minister pulls out the richest man who has appeared before the court so far and is still alive and beheads him for being corrupt. Since the rich are more likely to be corrupt, he hopes to get rid of most of the corrupt and the king is happy as he sees his policy being implemented enthusiastically.
Suppose the wealth of the citizens trooping into the court is
1376518911241376518911241\; 3\; 7\; 6\; 5\; 18\;  9\; 11\;  2\; 4
and the king walked in three times: the first time after the first four persons have seen the minister, the second time after the first five persons have seen the minister and, finally after the first nine persons have seen the minister.
At the king's first visit the richest person to have met the minister has wealth $7$ and he would be beheaded. At the second visit, the wealth of the richest person who has met the minister and is still alive has wealth $6$ and so he would be beheaded. At the third visit the richest person to have met the minister who is still alive has wealth $18$ and so he would be beheaded.
You may assume that the input is such that whenever the king walks in, it is always possible to behead someone.
Your aim is to write a program that will enable the prime minister to identify the richest man to have met the minister and who is still alive quickly. You may assume that no two citizens have the same wealth.

-----Input:-----
The first line of the input consists of two numbers $N$ and $M$, where $N$ is the number of citizens in the kingdom and M is the number of visits to the court by the king.
The next $N+M$ lines describe the order in which the $N$ citizens' appearances are interleaved with the $M$ visits by the king. A citizen's visit is denoted by a positive integer, signifying his wealth. You may assume that no two citizens have the same wealth. A visit by the king is denoted by $-1$.

-----Output:-----
Your output should consist of $M$ lines, where the $i^{th}$ line contains the wealth of the citizen who is beheaded at the $i^{th}$ visit of the king.

-----Constraints:-----
- $1 \leq M \leq 10000$.
- $1 \leq N \leq 100000$.
- You may assume that in $50 \%$ of the inputs $1 \leq M \leq 1000$ and $1 \leq N \leq 8000$.

-----Sample Input-----
10 3
1 
3 
7 
6 
-1 
5 
-1 
18 
9 
11
2
-1
4

-----Sample Output-----
7
6
18

Difficulty: interview

Starter code:

Solutions:
n,m=map(int,input().split())
l=[]
leng=0
for i in range(n+m):
    w=int(input())
    if w==-1:
        cm=0
        mi=0
        for j in range(leng):
            if l[j]>cm:
                cm=l[j]
                mi=j
        
        print(cm)
        l[mi]=-1
    else:
        l.append(w)
        leng+=1

(N,M) = map(int,input().split(' '))
S = []
for i in range(N+M):
    x = int(input())
    if x != -1:
        S.append(x)
    else:
        n = max(S)
        print(n)
        S.remove(n)

import bisect
n,m = map(int,input().split())
lst = []
ans = []
a = int(input())
lst.append(a)
for i in range(1,n+m):
    x = int(input())
    if x == -1:
        y = lst.pop(-1)
        ans.append(y)
    else:
        index = bisect.bisect_right(lst,x)
        lst.insert(index,x)
for i in ans:
    print(i)

########################################################
################# Template #############################
import sys
import math
def Int(): return int(input())
def Str(): return input()
def Ints(): return map(int,input().split(" "))
def int_arr(): return list(map(int,input().strip().split(" ")))
def str_arr(): return list(map(str,input().split(" ")))
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
#########################################################
#vsInput()
no_of_citizen, visits = Ints()
citizen_lst = []
maxi = 0
for i in range(no_of_citizen+visits):
    a = Int()
    if a==-1:
        print(citizen_lst[0])
        citizen_lst.pop(0)
    else:
        citizen_lst.append(a)
        citizen_lst = sorted(citizen_lst,reverse=True)

########################################################
################# Template #############################
import sys
import math
def Int(): return int(input())
def Str(): return input()
def Ints(): return map(int,input().split(" "))
def int_arr(): return list(map(int,input().strip().split(" ")))
def str_arr(): return list(map(str,input().split(" ")))
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
#########################################################
#vsInput()
no_of_citizen, visits = Ints()
citizen_lst = []
maxi = 0
for i in range(no_of_citizen+visits):
    a = Int()
    if a!=-1:
        citizen_lst.append(a)
        if a>maxi:
            maxi = a
    else:
        print(maxi)
        citizen_lst.remove(maxi)
        maxi = max(citizen_lst)

########################################################
################# Template #############################
import sys
import math
def Int(): return int(input())
def Str(): return input()
def Ints(): return list(map(int,input().split(" ")))
def int_arr(): return list(map(int,input().strip().split(" ")))
def str_arr(): return list(map(str,input().split(" ")))
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
#########################################################
#vsInput()
no_of_citizen, visits = Ints()
citizen_lst = []
for i in range(no_of_citizen+visits):
    a = Int()
    if a!=-1:
        citizen_lst.append(a)
    else:
        print(max(citizen_lst))
        index_max = citizen_lst.index(max(citizen_lst))
        citizen_lst.pop(index_max)




########################################################
################# Template #############################
import sys
import math
def Int(): return int(input())
def Str(): return input()
def Ints(): return list(map(int,input().split(" ")))
def int_arr(): return list(map(int,input().strip().split(" ")))
def str_arr(): return list(map(str,input().split(" ")))
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
#########################################################
#vsInput()
no_of_citizen, visits = Ints()
citizen_lst = []
for i in range(no_of_citizen+visits):
    a = Int()
    if a!=-1:
        citizen_lst.append(a)
    else:
        print(max(citizen_lst))
        citizen_lst.remove(max(citizen_lst))
        



from heapq import heappush, heappop
try:
    # Getting n, m, then initialising the lists
    n, m = list(map(int, input().split()))
    normal = []
    exe = []
    # As the problem states, we should do this n+m times.
    for i in range(0, (n+m)):
        get = int(input())
        # If the king has come, return the smallest(but biggest) element
        # For executing.
        if get==-1:
            c = -heappop(normal)
            exe.append(c)
        # Otherwise, push the negative value to normal
        else:
            heappush(normal, -get)
    # For loop to iterate through the executed people, and print them
    z = len(exe)
    for j in range(0, z):
        print(exe[j])
except:
    pass


from heapq import heappush, heappop
try:
    # Getting n, m, then initialising the lists
    n, m = list(map(int, input().split()))
    normal = []
    exe = []
    # As the problem states, we should do this n+m times.
    for i in range(0, (n+m)):
        get = int(input())
        # If the king has come, return the smallest(but biggest) element
        # For executing.
        if get==-1:
            c = -heappop(normal)
            exe.append(c)
        # Otherwise, push the negative value to normal
        else:
            heappush(normal, -get)
    # For loop to iterate through the executed people, and print them
    z = len(exe)
    for j in range(0, z):
        print(exe[j])
except:
    pass


from heapq import heappush, heappop
try:
    n, m = list(map(int, input().split()))
    normal = []
    exe = []
    for i in range(0, (n+m)):
        get = int(input())
        if get==-1:
            c = -heappop(normal)
            exe.append(c)
        else:
            heappush(normal, -get)
    for j in exe:
        print(j)
except:
    pass


from bisect import insort

n, m = list(map(int, input().split()))
pos = []
count = 0

while count < m:
    i = int(input())
    if i > 0: insort(pos, i)
    else:
        print(pos.pop(-1))
        count += 1


n, m = map(int, input().split())

pos = []
num = 0
while num < m:
    i = int(input())
    if i > 0: pos.append(i)
    else:
        print(max(pos))
        pos.remove(max(pos))
        num += 1

n, m = map(int, input().split())

iArr = []
for _ in range(n + m):
    i = int(input())
    if i != -1: iArr.append(i)
    else:
        print(max(iArr))
        iArr.remove(max(iArr))

n,m=map(int,input().split())

lis=[]
for i in range(n+m):
    k=int(input())
    if k==-1:
        lis.sort()
        print(lis.pop())
        
    else:
        lis.append(k)

n,m=map(int,input().split())

lis=[]
for i in range(n+m):
    k=int(input())
    if k==-1:
        lis.sort()
        print(lis.pop())
        
    else:
        lis.append(k)

n,m=map(int,input().split())

lis=[]
for i in range(n+m):
    k=int(input())
    if k==-1:
        print(str(max(lis)))
        lis.remove(max(lis))
    else:
        lis.append(k)

# cook your dish here
import heapq
n,m=map(int,input().split())
a=[]
for i in range(n+m):
	x=int(input())
	if(x==-1):
		ans=heapq.heappop(a)
		print(-ans)
	else:
		heapq.heappush(a,-x)

try:
    N, M = list(map(int, input().split()))
    L = []
    for i in range(N+M):
        a = int(input())
        if a != -1:
            L.append(a)
        else:
            print(max(L))
            L.remove(max(L))
except:
    pass
    


try:
    N, M = list(map(int, input().split()))
    L = []
    for i in range(N+M):
        L.append(int(input()))
    l = []
    for i in L:
        if i != -1:
            l.append(i)
        else:
            print(max(l))
            l.remove(max(l))
except:
    pass
    


# cook your dish here
import heapq
a, b = list(map(int, input().split()))
numList = []
for i in range(a+b):
    numIn = int(input())
    if numIn == -1:
        ans = heapq.heappop(numList)
        print(-ans)
    else:
        heapq.heappush(numList, -numIn)



[n,m]=list(map(int,input().split()))
l = []
for _ in range(n+m):
    t = int(input())
    if t == -1:
        print(max(l))
        l.remove(max(l))
    else:
        l.append(t)

a, b = map(int, input().split())
k = []
for _ in range(a + b):
    p = int(input())
    if p != -1:
        k.append(p)
    else:
        print(max(k))
        k.remove(max(k))

# cook your dish here
n,m=map(int,input().split())
t=n+m
l=[]
while t>0:
    a=int(input())
    if a!=-1:
        l.append(a)
    else:
        l.sort()
        print(l[-1])
        l[-1]=0
    t=t-1

# cook your dish here
n,m=map(int,input().split())
t=n+m
l=[]
while t>0:
    a=int(input())
    if a!=-1:
        l.append(a)
    else:
        l.sort()
        print(l[-1])
        l[-1]=0
    t=t-1

citizens, visits = list(map(int, input().split()))
total = citizens + visits
l = []
for i in range(total):
    n = int(input())
    if n == -1:
        l.sort()
        print(l[-1])
        l[-1] = 0
    else:
        l.append(n)