Lavinia are o afinitate pentru permutări, aşa că ea împreună cu Andrei au propus următorul joc.
Cerinţă
Dându-se un număr N şi N+1 elemente din mulţimea {0, 1, -1} trebuie să generaţi o permutare de lungime 2*N+1, care să respecte următoarele condiţii:
• Dacă elementul x din şirul dat este 0, mediana primelor 2*x-1 elemente din permutare trebuie să fie egală cu media primelor 2*x-1 elemente din permutare.
• Dacă elementul x din şirul dat este 1, mediana primelor 2*x-1 elemente din permutare trebuie să fie mai mică decât media primelor 2*x-1 elemente din permutare.
• Dacă elementul x din şirul dat este -1, mediana primelor 2*x-1 elemente din permutare trebuie să fie mai mare decât media primelor 2*x-1 elemente din permutare.
Date de intrare
În fişierul de intrare permutare.in se găseşte numărul natural N cu semnificaţia din enunţ. Pe următoarea linie se vor afla N + 1 numere din mulţimea {0, 1, -1} având seminificaţia din enunţ.
Date de ieşire
În fişierul de ieşire permutare.out se vor găsi 2*N+1 numere naturale reprezentând elementele permutării cerute.
Restricţii
• N ≤ 100 000
Exemple
permutare.in
permutare.out
Explicaţii
4
0 -1 0 1 0
5 1 8 2 9 4 7 3 6
Pentru primele 3 elemente media este 14/3 = 4.66, iar mediana 5, deci mediana este mai mare decât media.
Pentru primele 5 elemente media este 25/5, iar mediana 5, deci mediana este egală cu media.
Pentru primele 7 elemente media este 36/7 = 5.1, iar mediana este 5, deci media este mai mare decât mediana.