Problem D
Dans

Par Lindy hop dansara.

Röðin utan við vinsælasta Lindy hop stað borgarinnar er lengri en hún hefur nokkurn tímann verið! Þar sem öryggisleit og jakkafrágangur tekur þónokkurn tíma byrjar tónlistin og dansið um leið og fyrsta parið er komið á dansgólfið, þrátt fyrir að flest pör standi enn og bíði í röð.

Þrátt fyrir að Lindy hop er dans með einum dansfélaga er algengt að skipta um dansfélaga milli dansa. Lindy hop felur í sér þónokkra fimleika, kast og snúninga og er skemmtilegastur þegar danspar er af svipaðri hæð. Þar af leiðandi endurraða dansarar sér í ný pör hvert sinn sem nýtt par kemst inn á dansgólfið. Hversu vel geta dansararnir raðað sér saman í pör ef þeir velja dansfélaga með besta hætti svo þeir lágmarki mesta hæðamismun allra danspara á dansgólfinu?

Í pardansi eru þátttakendur oft með ólík hlutverk, til dæmis “leiðandi” og “fylgjandi”. Hér munum við gera ráð fyrir að sérhver gestur er annað hvort leiðandi eða fylgjandi og sérhvert par samanstendur af einum leiðanda og einum fylgjanda. Formlega má segja að ef eftir að $i$ pör eru komin á dansgólfið erum við með leiðendur af hæðum $l_1$, $\ldots ,$ $l_i$ og fylgjendur af hæðum $f_1$, $\ldots ,$ $f_i$. Þá viljum við lágmarka

yfir allar umraðanir $\pi $ á $\{ 1,\ldots , i\} $.

Input

• Ein lína með tölu $n\in \{ 1,\ldots , 25\, 000\} $, fjölda para.

• Svo $n$ línur, $i$-ta þeirra inniheldur hæðirnar $l_i, f_i\in \{ 50,\ldots , 250\} $ á leiðandi og fylgjandi $i$-ta parsins.

Output

Fyrir sérhvert $i$, prentið minnsta hæðarmismun milli danspara sem hægt er að ná með því að para saman fyrstu $i$ pörunum með sem besta hætti.

2
183 175
176 180

8
3

1
183 185

2