Problem
Carol Danvers, conocida como la Capitana Marvel, se opone a la flota Skrull. Cada uno de
Las naves Skrull tienen una cierta cantidad de poder expresada como un número natural.
Carol cree que es tan fuerte que no solo puede desactivar la flota, sino también un poco
diviértete. Después de estudiar detenidamente el poder de la nave, decidió desactivarlos
en el siguiente orden: cada vez que Carol atacará el barco que no fue atacado antes,
cuya potencia es la mediana de la potencia de los barcos restantes.
Carol calcula la mediana de una serie de números de la siguiente manera:
• Si el número de números en la fila es impar, entonces la mediana — el número en el medio de la serie dada ordenada en orden ascendente.
• Si el número de números en una fila es par, entonces la mediana de la fila es:
– El menor de los dos números en el medio de la serie dada, ordenados en orden ascendente, si los dos números del medio son diferentes.
– Cualquiera de los dos números en el medio de la serie dada, ordenados en orden ascendente,
si dos medias son iguales.
Ayuda al Capitán Marvel a determinar el orden en el que atacar los barcos.
Formato de datos de entrada
La primera línea contiene un número natural n — número de barcos en la flota Skrull (1 <= n <= 105).
La segunda línea contiene n números naturales ai — potencia de la i-ésima nave (1 <= ai <=109).
Formato de salida
Imprimir n números — el poder de las naves en el orden en que Carol las atacará.
| Entrada |
Salida |
|
3
8 3 19
|
8 3 19 |
|
4
4 2 2 1
|
2 2 1 4 |