Finále

A: Barikády

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Kosmonauti opevňují svoji vesmírnou základnu před útokem mimozemšťanů. Chtějí postavit do řady N barikád s velikostmi a1, a2,..., aN.

Mimozemský útok probíhá tak, že mimozemšťané přistanou na první barikádě a pak postupně přelézají na další barikády a snaží se dostat až na tu poslední, aby mohli sežrat kosmonauty. Na další barikádu můžou přelézt, pokud je stejně vysoká jako ta předchozí. Kromě toho se při výstupu z lodi rozhodnou, jestli si s sebou vezmou jetpacky, nebo boty, které je chrání při dopadu, oboje najednou neunesou. Podle toho potom můžou na další barikádu buď pouze stoupat, nebo pouze klesat.

Poraďte kosmonautům, jak mají seřadit barikády, aby se mimozemšťani na poslední barikádu nedostali.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů.

Každý problém je zadán číslem N na samostatném řádku, počtem barikád. Následuje N řádků obsahujících jedno číslo, každé reprezentuje výšku jedné barikády. Velikost každé barikády je nezáporné číslo, které se vejde do 32-bitového integeru.

Tvar výstupu

Na každém řádku vypište řešení jednoho problému – posloupnost barikád, kterou mimozemšťané nepřelezou. Pokud taková posloupnost neexistuje, vypište -1.

Lehká verze

  • T ≤ 200
  • 0 ≤ N ≤ 100
  • Všechny výšky barikád jsou unikátní.

Těžká verze

  • T ≤ 200
  • 0 ≤ N ≤ 1 000 000

Ukázkový vstup

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

Ukázkový výstup

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

Vysvětlení ukázkového vstupu a výstupu

V prvním problému uspořádáme barikády 2,1,3,4, takto se mimozemšťané zaseknou na 1. V druhém problému uspořádáme barikády 1,2,1, mimozemšťané se zaseknou na prostřední barikádě. Ve třetím problému už nemusíme nic dělat, mimozemšťané se zaseknou na 5, ale také můžeme barikády přeuspořádat podle obrázku.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)