Problem
Carol Danvers, conhecida como Capitã Marvel, combate a frota Skrull. Cada um
As naves Skrull têm uma certa quantidade de poder expressa como um número natural.
Carol se acha tão forte que pode não só desabilitar a frota, mas também um pouco
divirta-se. Depois de estudar cuidadosamente o poder do navio, ela decidiu que iria desativá-los
na seguinte ordem: cada vez que Carol atacar a nave que não foi atacada antes,
cuja potência é a mediana da potência das naves restantes.
Carol calcula a mediana de uma série de números da seguinte forma:
• Se o número de números na linha for ímpar, a mediana — o número no meio da série fornecida classificado em ordem crescente.
• Se o número de números em uma linha for par, a mediana da linha será:
– O menor dos dois números no meio da série dada, classificado em ordem crescente, se os dois números do meio forem diferentes.
– Qualquer um dos dois números no meio da série dada, classificados em ordem crescente,
se duas médias forem iguais.
Ajude a Capitã Marvel a descobrir a ordem de ataque aos navios.
Formato de dados de entrada
A primeira linha contém um número natural n — número de navios na frota Skrull (1 <= n <= 105).
A segunda linha contém n números naturais ai — potência do i-ésimo navio (1 <= ai <=109).
Formato de saída
Imprimir n números — o poder das naves na ordem que Carol irá atacá-las.
| Entrada |
Saída |
|
3
8 3 19
|
8 3 19 |
|
4
4 2 2 1
|
2 2 1 4 |