Coins

//package lol;
 
import java.util.*;
 
public class C {
 
	public static void main(String[] args) {
		Scanner io = new Scanner(System.in);
		int n = io.nextInt();
		TreeSet<Integer> l = new TreeSet<>();
		TreeSet<Integer> r = new TreeSet<>();
		List<Integer> backtrackActions = new ArrayList<>(2*n);
		for (int i=0; i<n; i++) {
			int coin = io.nextInt();
			int leftOrRight = io.nextInt();
			backtrackActions.add(coin);
			backtrackActions.add(leftOrRight);
			if (leftOrRight == 1) l.add(coin);
			else r.add(coin);
		}
		
		// asetetaan "to" se mis on isoin
		TreeSet<Integer> to = r;
		TreeSet<Integer> from = l;
		if (!l.isEmpty()) {
			if (r.isEmpty() || l.last() > r.last()) {
				to = l;
				from = r;
			}
		}
		Integer largest = to.last();
		
		
		// iterate vikavastaus -> actionit -> 2.vika vastaus -> actionit -> ...
		List<String> ans = new ArrayList<>(n);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		int countRemovedSmalls = 0;
		int i=backtrackActions.size()-1;
		while (true) {
			int smallestInFrom = (from.isEmpty() ? 0 : from.first());
			
			//System.out.println("smallestInFrom " + smallestInFrom);
			
			//System.out.println("to == r ? " + (to == r ? true : false));
			
			// vastaus
			int countSmallerThanFromSmallest = Math.max(0, smallestInFrom - 1 - countRemovedSmalls);
			int isojaMatchaavia = to.size() - countSmallerThanFromSmallest;
			
			//System.out.println("debug " + isojaMatchaavia + " " + from.size() + " " + countSmallerThanFromSmallest);
			
			if (isojaMatchaavia >= from.size()) ans.add(to == r ? "<" : ">");
			else ans.add("?");
			
			// actioni alkaa
			if (i <= 2) break;
			int leftOrRight = backtrackActions.get(i--);
			int coin = backtrackActions.get(i--);
			//System.out.println("Removing " + coin);
			
 
			if (coin < smallestInFrom) {
				to.remove(coin);
				countRemovedSmalls++;
			} else if (coin == smallestInFrom) {
				from.remove(coin);
				countRemovedSmalls++;
				int newSmallest = (from.isEmpty() ? 0 : from.first());
				while (!pq.isEmpty() && pq.peek() < newSmallest) {
					pq.poll();
					countRemovedSmalls++;
				}
			} else if (coin == largest) {
				to.remove(coin);
				largest = (to.isEmpty() ? null : to.last());
				//System.out.println("largest " + largest);
				if (largest == null || (!from.isEmpty() && from.last() > largest)) {
					// swap to and from
					TreeSet<Integer> helper = from;
					from = to;
					to = helper;
					largest = to.last();
				}
				pq.add(coin);
			} else {
				if (leftOrRight == 2) r.remove(coin);
				else l.remove(coin);
				pq.add(coin);
			}
		}
		
		Collections.reverse(ans);
		for (String s : ans) System.out.println(s);
	}
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED