Cambios en Arreglo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Alex tiene un arreglo a de N enteros y un entero K. Él puede cambiar cualquier par de elementos adyacentes del arreglo a lo más K veces. Alex quiere saber cuál es el mayor arreglo en orden lexicográfico que puede obtener. Ayúdalo.

Entrada

La primera línea contiene los enteros N y K \; (1 \leq N \leq 10^5; 0 \leq K \leq 5 \cdot 10^9). La segunda línea contiene N enteros a_i \; (0 \leq a_i \leq 10^9) separados entre sí por un espacio, estos son los elementos del arreglo.

Salida

En una única línea imprima los N elementos del mayor arreglo en orden lexicográfico que se puede obtener.

Ejemplos

Entrada 1
4 2
1 3 2 4
Salida 1
3 2 1 4
Entrada 2
4 3
1 3 2 3
Salida 2
3 3 1 2
Entrada 3
6 6
1 2 2 3 2 3
Salida 3
3 2 2 2 1 3
Entrada 4
6 7
1 2 2 3 2 3
Salida 4
3 3 1 2 2 2

Explicación de los ejemplos

En el primer ejemplo lo mejor es cambiar los pares de posiciones (1, 2) y (2, 3) en este orden.

En el segundo ejemplo lo mejor es cambiar los pares de posiciones (1, 2), (3, 4) y (2, 3) en este orden.

Nota

Un arreglo a de tamaño n es lexicográficamente mayor que un arreglo b de tamaño n si existe un k < n tal que a_1 = b_1, a_2 = b_2, \ldots, a_k = b_k y a_{k + 1} > b_{k + 1}.


Comments

There are no comments at the moment.