Problem D
Dans

Et par lindyhopdansere.

Køen uden for byens mest populære lindyhop-sted er længere end nogensinde før! Fordi sikkerhedstjek og garderobe tager betydelig tid, begynder musikken og dansen, så snart det første par er på dansegulvet, selvom de fleste stadig står i kø.

Lindyhop danses med en enkelt partner, men det er almindeligt at skifte partner mellem dansene. Lindyhop indebærer masser af akrobatik, som kast og snurreture, og det er sjovest at danse med nogen på omtrent samme højde. Derfor organiserer gæsterne sig hurtigt i par af lignende højde, hver gang et nyt par indtager dansegulvet. Hvor godt kan det gøres, hvis danserne skifter partnere optimalt for at minimere den største højdeforskel mellem de nuværende par i lokalet?

I pardans har deltagerne forskellige roller, kaldet »fører« og »følger«. I denne opgave er hver gæst enten fører eller følger, og hvert par består af én fører og én følger. Nærmere bestemt, efter at $i$ par er kommet ind, består lokalet af førere med højder $l_1$, $\ldots ,$ $l_i$ og følgere med højder $f_1$, $\ldots ,$ $f_i$. Opgaven er at minimere

over alle permutationer $\pi $ af $\{ 1, \ldots , i\} $.

Input

• En linje med antallet $n \in \{ 1, \ldots , 25\, 000\} $ af par.

• $n$ linjer, hvor den $i$te linje indeholder højderne $l_i, f_i \in \{ 50, \ldots , 250\} $ af hhv. føreren og følgeren i det $i$te par.

Output

For hvert $i$ skal du udskrive den mindste maksimale højdeforskel, der kan opnås i en optimal parring af de første $i$ par.

2
183 175
176 180

8
3

1
183 185

2