Concert Tickets

#include <bits/stdc++.h>
 
using namespace std;
 
// variables used for the current problem
int n, m, h, t;
multiset<int> tickets;
 
void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> h;
		tickets.insert(h);
	}
	for (int i = 0; i < m; ++i) {
		cin >> t;
		auto it = tickets.upper_bound(t);
		if (it == tickets.begin()) {
			cout << -1 << "\n";
		} else {
			cout << *(--it) << "\n";
			tickets.erase(it);
		}
	}
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

import java.io.*;
import java.util.*;
 
public class ConcertTickets {
	public static void main(String[] args) throws IOException {
		Reader io = new Reader();
		PrintWriter pw = new PrintWriter(System.out);
 
		int ticketNum = io.nextInt();
		int peopleNum = io.nextInt();
		// No multiset in java so we'll have to use a TreeMap
		NavigableMap<Integer, Integer> ticketMultiset = new TreeMap<>();
		Map.Entry<Integer, Integer> val;
 
		for (int i = 0; i < ticketNum; i++) {
			int priceOfTicket = io.nextInt();
			/*
			 * If the set already contains the same key value,
			 * create another pair next to it
			 */
			if (ticketMultiset.containsKey(priceOfTicket)) {
				ticketMultiset.put(priceOfTicket,
				                   ticketMultiset.get(priceOfTicket) + 1);
			} else {
				ticketMultiset.put(priceOfTicket, 1);
			}
		}
 
		for (int i = 0; i < peopleNum; i++) {
			int customerMaxPrice = io.nextInt();
			/*
			 * Get the optimal ticket for this customer
			 * We add 1 because lowerEntry returns the highest
			 * *strictly* lower entry
			 */
			val = ticketMultiset.lowerEntry(customerMaxPrice + 1);
			// If there are no possible prices, we can exit and return -1
			if (val != null) {
				pw.println(val.getKey());
				/*
				 * If there's more than one set with the key value,
				 * then replace the current set with
				 * the next-lowest set with the same key
				 */
				if (val.getValue() == 1) {
					ticketMultiset.remove(val.getKey());
 
				} else {
					ticketMultiset.put(val.getKey(), val.getValue() - 1);
				}
			} else {
				pw.println(-1);
			}
		}
		io.close();
		pw.close();
	}
	// Kattio is too slow
	// BeginCodeSnip{Fast Reader}
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;
 
		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1) buffer[0] = -1;
		}
 
		private byte read() throws IOException {
			if (bufferPointer == bytesRead) fillBuffer();
			return buffer[bufferPointer++];
		}
 
		public void close() throws IOException {
			if (din == null) return;
			din.close();
		}
		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');
 
			if (neg) return -ret;
			return ret;
		}
	}
	// EndCodeSnip{}
}

import sys
from bisect import *
 
sys.setrecursionlimit(200000)
 
 
def get_endpoint(idx: int) -> int:
	if idx == -1 or idx == endpoints[idx]:  # idx is the root
		return idx
	endpoints[idx] = get_endpoint(endpoints[idx])  # find the root of its parent
	return endpoints[idx]
 
 
n, m = map(int, input().split())
h = sorted(int(i) for i in input().split())  # price of tickets
t = [int(i) for i in input().split()]  # max price for each customer
endpoints = list(range(n))
for i in t:
	pos = get_endpoint(bisect(h, i) - 1)
	if pos >= 0:
		print(h[pos])
		endpoints[pos] = pos - 1
	else:
		print(-1)