Problem G
Netþjónapláss

Mynd eftir Victor Grigas, commons.wikimedia.org

Þörf er á að endurskipuleggja tölvuherbergið og því miður lenti það á þér að sjá um það. Eins skýjað og er alltaf hér í borg óttans mætti halda að hægt væri að koma fyrir þessum tölvum í skýjunum, en það er alltaf talið of dýrt þegar þú nefnir það við stjórnendur.

Jæja, það er þá bara að grafa upp gömlu teikningarnar af því hvar allt er og hvernig það er fest við vegginn. Allir tölvuskáparnir standa meðfram einum vegg og hver skápur nær frá golfi og nokkurn veginn upp í loft. Þú veist líka að skápurinn lengst til vinstri liggur upp við vegg og svo liggja tölvuskáparnir upp við hvorn annann með engum bilum á milli.

Þú vilt eyða sem minnstum tíma inn í tölvuherberginu, loftið er ógeðslegt og birtan léleg. Því miður gefa teikningarnar bara upp hvar skáparnir eru festir við veginn, sem er á miðjum skáp. Þig vantar hins vegar að vita hvað skáparnir eru víðir. Geturðu reiknað út breidd skápanna út frá þessu?

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölur $1 \leq N \leq 10^5$, fjöldi tölvuskápa. Næst fylgja $N$ línur, hver með heiltölu $1 \leq x \leq 10^9$, punkt þar sem skápur er festur við vegg.

Úttak

Prentið $N$ línur, hver með breidd eins tölvuskáps. Prentið breiddirnar í þeirri röð sem skáparnir koma fyrir á veggnum frá vinstri til hægri. Þú mátt gera ráð fyrir að til sé gild lausn þar sem allar breiddir eru stranglega jákvæðar.

Útskýringar á sýnidæmum

Figure 1: Mögulegt útlit sýnidæmis 1

4
12
7
18
3

6
2
8
4