Descripción

Se te da una permutación \(p\) de tamaño \(n\). Una permutación de tamaño \(n\) es un arreglo de tamaño \(n\) en el que cada entero de \(1\) a \(n\) aparece exactamente una vez. Por ejemplo, \([1,4,3,2]\) y \([4,2,1,3]\) son permutaciones correctas, mientras que \([1,2,4]\) y \([1,2,2]\) no lo son.

Consideremos una deque (cola de doble extremo) vacía. Una deque es una estructura de datos que permite añadir elementos tanto al principio como al final. Por lo tanto, si hay elementos \([1,5,2]\) en la deque, añadir un elemento \(4\) al principio generará la secuencia \([4,1,5,2]\), y añadir el mismo elemento al final generará \([1,5,2,4]\).

Los elementos de la permutación se añaden secuencialmente a la deque inicialmente vacía, comenzando con \(p_1\) y terminando con \(p_n\). Antes de añadir cada elemento a la deque, puedes elegir si desea añadirlo al principio o al final.

Por ejemplo, si consideramos una permutación \(p=[3,1,2,4]\), una de las posibles secuencias de acciones se ve así:

1. añadir \(3\) al final de la deque: la deque contiene la secuencia \([3]\);

2. añadir \(1\) al principio de la deque: la deque contiene la secuencia \([1,3]\);

3. añadir \(2\) al final de la deque: la deque contiene la secuencia \([1,3,2]\);

4. añadir \(4\) al final de la deque: la deque contiene la secuencia \([1,3,2,4]\);

Encuentra la secuencia lexicográficamente más pequeña posible de elementos en la deque después de procesar toda la permutación.

Una sucesión \([x_1,x_2,…,x_n]\) es lexicográficamente menor que la sucesión \([y_1,y_2,…,y_n]\) si existe tal \(i≤n\) que \(x_1=y_1\), \(x_2=y_2, … , x_{i-1}=y_{i-1}\) y \(x_i<y_i\). En otras palabras, si las secuencias \(x\) y \(y\) tienen algún prefijo coincidente (posiblemente vacío), y el siguiente elemento de la secuencia \(x\) es estrictamente menor que el elemento correspondiente de la secuencia \(y\). Por ejemplo, la secuencia \([1,3,2,4]\) es menor que la secuencia \([1,3,4,2]\) porque después de los dos elementos coincidentes \([1,3]\) al inicio, la primera secuencia tiene un elemento \(2\) que es menor que el elemento correspondiente \(4\) en la segunda secuencia.

Entrada

La primera línea contiene un entero \(t\) \((1≤t≤1000)\) \(-\) el número de casos de prueba.

Las siguientes \(2t\) líneas contienen descripciones de los casos de prueba.

La primera línea de la descripción de cada caso de prueba contiene un entero \(n\) \((1≤n≤2⋅10^5)\) \(-\) el tamaño de la permutación. La segunda línea de la descripción contiene \(n\) enteros \(p_i\) \((1≤p_i≤n\); todos los \(p_i\) son únicos\()\) separados por espacios \(-\) elementos de la permutación.

Se garantiza que la suma de \(n\) en todos los casos de prueba no exceda \(2⋅10^5\).

Salida

Imprime \(t\) líneas, cada una con la respuesta al caso de prueba correspondiente. La respuesta a un caso de prueba debe contener \(n\) números enteros separados por espacios \(-\) los elementos de la permutación lexicográficamente más pequeña que es posible encontrar en la deque después de ejecutar el algoritmo descrito.

Ejemplo

Entrada

5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

Salida

1 3 2 4 
1 2 3 
1 3 2 
1 2 
1 2

Nota

Una de las formas de obtener la permutación lexicográficamente más pequeña \([1,3,2,4]\) a partir de la permutación \([3,1,2,4]\) (el primer caso de prueba de muestra) se describe en el enunciado del problema.