Problem D
Dance

A couple of Lindy Hop dancers.

The line outside the city’s most popular Lindy Hop venue is longer than ever! Because security and coat checking takes significant time, the music and dancing starts as soon as the first couple hits the floor, even though most couples are still standing in line.

Although Lindy Hop is danced with a single partner, it is common to swap partners between dances. Lindy Hop involves lots of acrobatics, such as throwing and twirling, and is most fun to dance with somebody of similar height. Thus, every time a new couple checks into the venue, the guests quickly re-organise themselves into pairs of similar height. How well could the guests do if they swapped partners optimally and wanted to minimise the largest height difference of the pairs currently in the venue?

In pair dancing, participants have different roles referred to as “leader” and “follower”. For the purpose of this task each guest is either a leader or a follower and each couple consist of one leader and one follower. Formally, after $i$ couples have entered, the venue contains leaders of height $l_1$, $\ldots ,$ $l_i$ and followers of height $f_1$, $\ldots ,$ $f_i$. The task is to mimimise

over all permutations $\pi $ on $\{ 1,\ldots , i\} $.

Input

• One line with the number $n\in \{ 1,\ldots , 25\, 000\} $ of couples.

• $n$ lines, the $i$th of which contains the heights $l_i, f_i\in \{ 50,\ldots , 250\} $ of the $i$th couple’s leader and follower.

Output

For each $i$, output the smallest maximum height difference between couples that can be achieved by pairing the first $i$ couples optimally.

2
183 175
176 180

8
3

1
183 185

2