We're looking to design a data structure that holds pairs of numbers and can answer queries of the form "Which pair has both numbers larger than a given pair, but so that the second number differs by as little as possible?". One such data structure is an order-statistic tree (also called tournament tree).

In general, a tournament tree is a complete binary tree whose leaves hold data, while each node higher in the tree holds some desired statistic about the leaf nodes contained in the subtree rooted at that node: for example the smallest number, largest number, sum of numbers etc.

In this problem we'll have the nodes hold the largest number in their subtree. The root node thus holds the largest number of all the leaves, its left child holds the largest in the first half of the sequence etc. The tree is stored in an array so that the children of node ~x~ are at indices ~2x~ and ~2x+1~. The parent of node ~x~ is ~x/2~ (division truncates).

When adding the pair ~(a, b)~ to the tree, we write the value ~a~ on the ~b^{th}~ leaf node, and climb up the tree, updating the higher nodes.

The tree can tell us the first number larger than the one in leaf node ~x~, located in the tree to the right of node ~x~. The algorithm is:

• Start from the root node (consider the entire tree)
• Repeat:
  • If ~x~ is not in the subtree rooted at the current node, then none of these nodes are right of ~x~ so there is no solution in that subtree
  • If ~x~ is in the right subtree, move to that subtree (no nodes in the left subtree are right of ~x~)
  • Otherwise (~x~ is in the left subtree), if the left subtree contains a number larger than ~x~, try to find the first one right of ~x~ (recursive call) – otherwise, find the leftmost number larger than ~x~ in the right subtree

It takes some convincing, but working out the cases reveals that the complexity of one query is ~\mathcal O(\log N)~, so the complexity of the entire algorithm is ~\mathcal O(N \log N)~.

One final observation is that the numbers ~b~ are too large to be held in the tree. This can be remedied by sorting all students by the number ~b~, then replacing all numbers ~b~ with the indices in the sorted sequence: the smallest number ~b~ is changed to ~1~, the second smallest to ~2~ etc. We can do this because the rest of the algorithm only cares about their relative ordering, not the absolute values. This procedure is referred to as compressing the input data.