BOJ. Data Structure (12899)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static int[] seg;
	static int[] orig;
	static final int N = 2000000;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[] line;
		int n = toi(br.readLine());
		seg = new int[1 << (int)Math.ceil(Math.log(N) / Math.log(2)) + 1];
		for(int i = 0; i < n; i++) {
			line = getArr();
			if(line[0] == 1) {
				update(1, N, 1, line[1]);
			}
			else {
				int[] result = get(1, N, 1, line[1]);
				int targetIdx = result[0], val = result[1];
				sb.append(val).append("\n");
				delete(1, N, 1, val);
			}
		}
		print(sb);
	}

	static void update(int left, int right, int idx, int target) {
		if(target < left || right < target) return;
		seg[idx]++;
		if(left == right) return;
		int mid = (left + right) / 2;
		update(left, mid, 2 * idx, target);
		update(mid + 1, right, 2 * idx + 1, target);
	}

	static void delete(int left, int right, int idx, int target) {
		if(target < left || right < target) return;
		seg[idx]--;
		if(left == right) return;
		int mid = (left + right) >> 1;
		delete(left, mid, idx << 1, target);
		delete(mid + 1, right, idx << 1 | 1, target);
	}

	static int[] get(int left, int right, int idx, int leftNum) {
		if(left == right) return new int[] { idx, left }; //leftNum might not be 0 if there's duplicated value.
		int mid = (left + right)>>1;
		if(seg[idx << 1] >= leftNum) {
			return get(left, mid, idx << 1, leftNum);
		}
		else {
			return get(mid + 1, right, idx << 1 | 1, leftNum - seg[idx << 1]);
		}
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}