Ježko Pichliač mal nedávno narodeniny. A ako darček dostal od svojej mamy postupnosť celých čísel. Bohužiaľ, táto postupnosť sa ježkovi hrozne nepáčila. Rozhodol sa ju zmeniť, nechcel však zarmútiť svoju mamu, preto si povedal, že zmení práve jedno číslo. Pre každú pozíciu $i$ by ho teraz zaujímalo, aké najmenšie číslo môže byť na $i$-tom mieste, ak v pôvodnej postupnosti zmení jeden prvok a túto postupnosť utriedi vzostupne.
Na vstupe dostanete postupnosť celých čísel z rozsahu $1$ až $10^9$. Jedno číslo tejto postupnosti musíte nahradiť iným číslom. Nové číslo musí byť iné, ako to staré a musí opäť ležať v intervale $1$ až $10^9$. Pre každú pozíciu vypíšte, aké najmenšie číslo sa môže nachádzať na danej pozícii po výmene jedného čísla a zoradení postupnosti.
Na prvom riadku je číslo $n \, (1 \leq n \leq 10^5)$ – počet čísel v postupnosti. Na druhom riadku je $n$ celých čísel z rozsahu $1$ až $10^9$, určujúce postupnosť
Na jeden riadok vypíšte n medzerou odelenných čísel. $i$-te číslo určuje najmenšie číslo, ktoré môže byť na $i$-tej pozícii.
5
4 7 2 1 6
1 1 2 4 6