Problem
Carol Danvers, conosciuta come Captain Marvel, contrasta la flotta Skrull. Ciascuno di
Le navi Skrull hanno una certa quantità di potenza espressa come numero naturale.
Carol pensa di essere così forte da poter non solo disabilitare la flotta, ma anche un po'
divertiti. Dopo aver studiato attentamente la potenza della nave, decise che li avrebbe disattivati
nel seguente ordine: ogni volta che Carol attaccherà la nave che non è stata attaccata prima,
la cui potenza è la mediana della potenza delle restanti navi.
Carol calcola la mediana di una serie di numeri come segue:
• Se il numero di numeri nella riga è dispari, la mediana — il numero al centro della serie data ordinata in ordine crescente.
• Se il numero di numeri in una riga è pari, la mediana della riga è:
– Il più piccolo dei due numeri al centro della serie data, ordinato in ordine crescente, se i due numeri al centro sono diversi.
– Uno qualsiasi dei due numeri al centro della serie data, ordinati in ordine crescente,
se due medie sono uguali.
Aiuta Captain Marvel a capire l'ordine in cui attaccare le navi.
Formato dei dati di input
La prima riga contiene un numero naturale n — numero di navi nella flotta Skrull (1 <= n <= 105).
La seconda riga contiene n numeri naturali ai — potenza della nave i-esima (1 <= ai <=109).
Formato di output
Stampa n numeri — la potenza delle navi nell'ordine in cui Carol le attaccherà.
| Input |
Uscita |
|
3
8 3 19
|
8 3 19 |
|
4
4 2 2 1
|
2 2 1 4 |