Finále

A: Diplomatická mise

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í)

Na Ústředí Kasiopey se slaví nebývalý úspěch: podařilo se objevit první exoplanetu s pravděpodobným výskytem života! Proto generál Kája připravuje diplomatickou misi s cílem seznámit se s obyvateli exoplanety S2. Ovšem letět na planetu, o níž moc nevíte se mnoha lidem nechce. Celkem se může této mise zúčastnit N diplomatů, ale každý diplomat je jinak statečný. Míru jeho odvahy (nebo spíše zbabělosti) určuje číslo, které říká, kolik diplomatů se už muselo rozhodnout k účasti na misi, aby odletěl i tento. Tedy pokud má diplomat zbabělost 0, vždy se mise zúčastní. Pokud má zbabělost 3, znamená to, že odletí pouze pokud se už tři další diplomati rozhodli, že poletí. Vaším úkolem je zjistit, kolik diplomatů se mise zúčastní.

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů. Každý problém má na prvním řádku číslo N udávající celkový počet diplomatů. Na dalším řádku následuje N nezáporných čísel oddělených mezerami, které udávají zbabělosti jednotlivých diplomatů.

Tvar výstupu

Pro každý problém vypište na samostatný řádek jedno číslo - počet diplomatů, kteří se zúčastní mise.

Lehká verze

  • T ≤ 10
  • N ≤ 1 000
  • zbabělosti ≤ 1 000

Těžká verze

  • T ≤ 10
  • N ≤ 300 000
  • zbabělosti ≤ 1 000 000 000

Ukázkový vstup

2
5
2 6 1 4 0
3
1 2 3

Ukázkový výstup

3
0

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

V prvním vstupu se k účasti nejprve přihlásí pátý diplomat (se zbabělostí 0). Díky tomu se k účasti odváží i třetí diplomat, který má zbabělost 1. A protože už poletí 2 diplomati, přidá se i diplomat se zbabělostí 2. Vidíme, že diplomati se zbabělostmi 4 a 6 se už nepřidají, protože počet jejich spolupracovníků je menší než jejich zbabělost.

V druhém vstupu nemáme žádného diplomata se zbabělostí 0, který by odletěl na misi i sám, takže se mise bude konat bez diplomatů.

Máš na to!

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