Ada Lovelace está explorando un bosque lleno de portales mágicos. Cada portal tiene un número mágico y aparece en un momento diferente del día.

Cada vez que aparece un nuevo portal, Ada quiere saber cuál es el mayor número mágico, entre los portales que ya aparecieron, que sea estrictamente menor al número mágico del portal actual. Si no existe tal portal, anota \(-1\).

Ayúdala a encontrar esa información para cada portal que aparece.

La primera línea contiene un entero \(N\) (\(1 \le N \le 10^5\)), la cantidad de portales mágicos.

La segunda línea contiene \(N\) enteros \(P_1, P_2, \ldots, P_N\) (\(1 \le P_i \le 10^9\)), donde \(P_i\) es el número mágico del portal que aparece en la posición \(i\).

Imprime una línea con \(N\) enteros separados por un espacio. El \(i\)-ésimo entero debe ser el número mágico más grande que apareció antes que \(P_i\) y que sea estrictamente menor que \(P_i\). Si no existe tal número, imprime \(-1\).

Explicación del ejemplo 1

• Para 3: no hay portales antes, resultado \(-1\).
• Para 1: no hay menores antes, resultado \(-1\).
• Para 4: 3 es el mayor menor.
• Para 2: 1 es el mayor menor.
• Para 5: 4 es el mayor menor.