Intercambios

Points: 100

Time limit: 1.0s

Memory limit: 512M

Authors:

leocar, Albe

Problem type

Allowed languages

C, C++, Java, Pascal, VB

Dada una secuencia de $n$ ~n~ números $x_1, x_2, ..., x_n$ ~x_1, x_2, ..., x_n~. Cada número $1, 2, ..., n$ ~1, 2, ..., n~ aparece exactamente una vez en la secuencia.

Puedes modificar la secuencia utilizando intercambios. Hay $n-1$ ~n-1~ turnos consecutivos numerados desde $k = 2, 3, ..., n$ ~k = 2, 3, ..., n~. En el turno $k$ ~k~, puedes intercambiar los valores $x_k$ ~x_k~ y $x_{\lfloor k/2 \rfloor}$ ~x_{\lfloor k/2 \rfloor}~ en la secuencia o no hacer nada.

La secuencia $a_1, a_2, ..., a_n$ ~a_1, a_2, ..., a_n~ es lexicográficamente más pequeña que la secuencia $b_1, b_2, ..., b_n$ ~b_1, b_2, ..., b_n~ si existe un índice $j$ ~j~ $(1 \leq j \leq n)$ ~(1 \leq j \leq n)~ tal que $a_k = b_k$ ~a_k = b_k~ para todo $k < j$ ~k < j~ y $a_j < b_j$ ~a_j < b_j~.

Debes encontrar la secuencia lexicográficamente mínima que se puede obtener realizando intercambios en la secuencia dada.

Entrada

La entrada consiste en dos líneas.

La primera línea contiene un entero $n$ ~n~ $(1 \leq n \leq 2 \cdot 10^5)$ ~(1 \leq n \leq 2 \cdot 10^5)~, la longitud de la secuencia.

La segunda línea contiene $n$ ~n~ enteros $x_1, x_2, ..., x_n$ ~x_1, x_2, ..., x_n~ $(1 \leq x_i \leq n, x_i \ne x_j\ para\ i \ne j)$ , los números en la secuencia.