Domácí kolo

C: Pošťák

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

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Do nově vybudovaného hangáru Mezinárodní Futuristické Flotily na planetě Ma-stra přiletěla poštovní loď. Všechny dopisy z této lodi má roznést pošťák Celestýn. Při příletu lodi dostane dopisy a soupis identifikačních čísel lodí, kam má dopisy roznést. Aby se nezamotal v tom, kam už dopisy roznesl, a jaké mu ještě zbývají, tak raději nejprve doručí první dopis z hromady, pak druhý a tak dále (tedy je nijak nepřerovnává).

Jenže to je strašně náročná práce a Celestýn navíc hned po roznesení dopisů odlétá na dovolenou. Také přišel na jednu zcela nesouvisející informaci, a to, že když čirou náhodou jeden dopis ztratí, tak si nikdo ničeho nevšimne. Bojí se ale, že kdyby se dopisů ztratilo víc, tak už někdo pojme podezření, že to není jen nešťastná náhoda.

Celestýn je ale optimista a na všem hledá něco dobrého. Uvědomil si tedy, že když se přihodí ta politováníhodná skutečnost, že se nějaký dopis ztratí, má to i jednu, nutno podotknout, že skoro nevýznamnou, kladnou stránku: Celestýn pak vůbec nemusí chodit k té lodi, kam dopis mířil a může se vydat hned k další vesmírné lodi. Celestýn by rád, jen tak pro zajímavost, zjistil, který dopis by měl ztratit, aby toho nachodil co nejméně (a tedy co nejdříve odletěl na svou, nepochybně zaslouženou, dovolenou).

V hangáru jsou vesmírné lodě seřazené podle identifikačního čísla jedna vedle druhé, vzdálenost mezi každými dvěma loďmi je přesně 20 metrů a vstup do lodi (s poštovní schránkou) je přesně uprostřed. Vzdálenost od vstupu lodi s identifikačním číslem 3 k lodi s identifikačním číslem 5 je tedy přesně 40 metrů.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit. Pro každý problém dostanete na prvním řádku jedno číslo N udávající počet míst, která musí Celestýn navštívit. Na dalším řádku bude N čísel oddělených mezerou – identifikační čísla daných vesmírných lodí. První z nich je identifikační číslo poštovní lodi, odkud Celestýn s dopisy vyráží. Následuje N−2 čísel lodí, kam Celestýn roznáší dopisy (které se v případě nešťastné náhody mohou ztratit) v pořadí, ve kterém je má roznést. Poslední číslo je číslo lodi, kam má Celestýn nastoupit, aby mohl odletět na svou dovolenou. Pozn.: Celestýn může nést více dopisů jedné lodi a tyto dopisy nemusí (a mohou) být v hromadě dopisů za sebou.

Tvar výstupu

Pro každý testovací vstup vypište jediný řádek, a to pořadové číslo hledaného dopisu. V případě, že existuje více stejně „výhodných“ dopisů, vypište libovolný z nich. Samotné dopisy číslujeme od jedničky, ale nezapomeňte, že řádek začíná číslem poštovní lodi, kam Celestýn dopis nenese.

Lehká verze

  • T ≤ 10
  • 3 ≤ N ≤ 1 000
  • 1 ≤ xi ≤ 1 000 000 000

Těžká verze

  • T ≤ 10
  • 3 ≤ N ≤ 1 000 000
  • 1 ≤ xi ≤ 1 000 000 000

Ukázkový vstup

2
3
31 23 82
5
13 14 15 11 12

Ukázkový výstup

1
2

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

V prvním vstupu má Celestýn roznést jediný dopis, takže odpovědí je tedy tento jediný dopis.

Ve druhém případě se už má Celestýn roznést dopisy tři. Nejméně se nachodí, pokud se ztratí druhý nebo třetí dopis, můžeme tedy vypsat třeba dvojku.

Máš na to!

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