Domácí kolo

F: Sedmikráska

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

Michala už nebaví pracovat od rána do večera na úlohách do Kasiopey. Utrhl proto na louce sedmikrásku s čísly na okvětních lístcích. Teď se chystá její lístky otrhat a na základě toho se rozhodnout, zda bude po zbytek dne pokračovat v těžké práci, nebo se projde po lese. To druhé by ho samozřejmě potěšilo více.

Michalova sedmikráska má N lístků a na i-tém z nich je napsáno přirozené číslo a_i. Michal si nejprve vybere nějaký startovní lístek \ell, přečte si hodnotu a_\ell, která je na něm napsaná, a otrhá a_\ell lístků sedmikrásky počínaje lístkem \ell ve směru hodinových ručiček. Následně se podívá na lístek za posledním utrhnutým (tedy lístek na pozici \ell+a_\ell, a pokud je toto číslo větší než N, tak \ell+a_\ell-N). Opět si přečte jeho hodnotu a opět otrhá tolik lístků ve směru hodinových ručiček. Takto pokračuje, dokud nejsou všechny lístky utrženy.

Pokud se v nějakou chvíli stane, že počet lístků, které sedmikrásce zbývají, je ostře menší než počet lístků, které chce Michal utrhnout, Michal půjde pokračovat v práci. Pokud se naopak někdy stane, že počet zbylých lístků je přesně roven počtu, který chce Michal otrhat, tak Michal otrhá tyto zbylé lístky a půjde se projít do lesa.

Existuje nějaká startovní pozice taková, že pokud na ní Michal začne, půjde na procházku do lesa?

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 číslo N. Na dalším řádku je N čísel; i-té z nich, a_i, je číslo napsané na i-tém lístečku sedmikrásky (lístečky jsou uvedeny po směru hodinových ručiček).

Tvar výstupu

Za každý problém vypište jeden řádek, na němž je napsáno ANO, pokud lze najít takovou počáteční pozici, aby Michal otrhal všechny lístky a mohl se projít, a NE, pokud taková pozice neexistuje.

Lehká verze

  • 1 \leq T \leq 15
  • 1 \leq N \leq 1000
  • Hodnota každého lístečku je nejvýše 10^6, tj. 1 \leq a_i \leq 10^6.

Těžká verze

  • 1 \leq T \leq 15
  • 1 \leq N \leq 10^6
  • Hodnota každého lístečku je nejvýše 10^6, tj. 1 \leq a_i \leq 10^6.

Ukázkový vstup

3
1
1
5
2 2 2 2 2
7
3 5 2 3 1 4 8

Ukázkový výstup

ANO
NE
ANO

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

V prvním problému má sedmikráska jen jeden lístek, na kterém je napsáno, že má Michal utrhnout jeden lístek. Michal jej utrhne a půjde do lesa.

V druhém problému nezáleží na tom, kde Michal začne s trháním; dvakrát utrhne dva lístky a poslední lístek mu řekne, že má utrhnout dva lístky. To ale nejde, neboť zbývá už jen jeden. Michal proto v tomto případě nikam nepůjde.

V posledním problému může Michal začít s šestým lístkem: utrhne čtyři lístky a dostane se ke třetímu lístku. Ten opět utrhne spolu s tím následujícím a dostane se k pátému lístku. Nakonec utrhne zbývající lístek a vydá se do lesa.

Máš na to!

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