A Ciutat Plana els edificis estan alineats en una sola avinguda. Cada edifici té una alçada representada per un nombre enter.

Com que és l'any 1984, l’ajuntament ha contractat un vigilant per evitar que la gent s'escapi de casa de nit, esquivant així el toc de queda.

La qüestió és que el vigilant contractat és una mica especialet (era l'únic que el partit únic es podia permetre) i per manies seves, no es disposa a treballar fins a saber, per a cada edifici, l'alçada del primer edifici més alt que té a l’esquerra.

Davant d'això el partit únic us demana que, per accelerar la feina, l'ajudeu a calcular-ho.

Objectiu

Fes un programa que, donada una seqüència de \(n\) edificis (\(1 \le n \le 1000000\)) amb les seves alçades:

\(a_1, a_2, ... a_n\)

generi una nova seqüència:

\(b_1, b_2, ... b_n\) on:

• \(b_i\) és l'alçada del primer edifici més alt a l’esquerra de \(a_i\)
• si no existeix cap edifici més alt a l’esquerra \(b_i\) val 0.

Entrada

• La primera línia té un enter amb el nombre de casos de prova on cadascun dels casos té dues línies.
• A la primera línia de cada cas hi ha un enter \(n\) amb el nombre d’edificis.
• A la segona línia de cada cas hi ha els \(n\) enters \(0 \le a_i \le 10^9\) que representen les alçades dels edificis.

Sortida

• Per a cada cas hi ha una línia amb \(n\) enters, la seqüència \(b\), amb la informació que demana el vigilant.

Exemple

Entrada

2
5
3 7 2 6 1
20
4 6 3 8 2 7 5 9 1 10 6 4 12 3 8 2 15 7 1 11

Sortida

0 0 7 7 6
0 0 6 0 8 8 7 0 9 0 10 6 0 12 12 8 0 15 7 15

Explicació

L'entrada té 2 casos:

• El cas 1 té 5 edificis
  • L’edifici de 3 no té ningú a l’esquerra → 0
  • El de 7 tampoc → 0
  • El de 2 veu el 7 → 7
  • El de 6 també veu el 7 → 7
  • El d’1 veu el 6 → 6
  • 0 0 7 7 6 és la sortida del cas 1
• El cas 2 té 20 edificis
  • Entrada: 4 6 3 8 2 7 5 9 1 10 6 4 12 3 8 2 15 7 1 11
  • Sortida: 0 0 6 0 8 8 7 0 9 0 10 6 0 12 12 8 0 15 7 15