Problem A
Av(1324)

Fimm dæmi komin, og komin hugmyndaþurrð hjá Arnari og Atla. Vanráða spyrja þeir aðra starfsmenn HR hvað skal leggja fyrir nemendur og eftir smá leit enda þeir á tali við Henning. Hann segir að “Pattern avoiding permutations” sé málið. Hann vill meina að ekkert sé áhugaverðara en að leysa gátuna um fjölda umraðana sem forðast mynstrið $1324$. “En er þetta ekki svolítið þungt fyrir þau? Þetta er óleyst verkefni!” segir Arnar. Eftir smá umræðu var ákveðið að frekar en að láta nemendur leysa það verkefni, þá þurfa þau bara að gá hvort umröðun forðist mynstrið.

Því kemur nú að þér! Inntakið gefur þér umröðun $\pi _1, \pi _2, \dots , \pi _ n$ á tölunum $1, 2, \dots , n$. Það þýðir að $\pi _1, \pi _2, \dots , \pi _ n$ eru tölurnar $1, 2, \dots , n$, bara mögulega í annarri röð. Að ákvarða hvort umröðunin innihaldi mynstrið $1324$ felst í því að athuga hvort til séu vísar $1 \leq i_1 < i_2 < i_3 < i_4 \leq n$ þannig að $\pi _{i_1} < \pi _{i_3} < \pi _{i_2} < \pi _{i_4}$.

Inntak

Fyrsta lína inntaksins inniheldur heiltölu $1 \leq q \leq 10^5$, fjöldi umraðana í inntaki. Næst fylgja $2q$ línur, hverjar tvær línur gefa eina umröðun. Fyrri línan inniheldur eina heiltölu $n_ i$, stærð umraðaninnar. Næsta lína inniheldur umröðunina $1 \leq \pi _1, \pi _2, \dots , \pi _ n \leq n_ i$ með bili milli talna. Lát $n$ vera samtals lengd allra umraðana í inntaki. Gefið er að $n \leq 10^6$.

Úttak

Fyrir hverja umröðun í inntakinu skal prenta eina línu. Ef mynstrið kemur ekki fyrir skal prenta “Ekkert mynstur!”. Annars skal prenta vísa $1 \leq i_1 < i_2 < i_3 < i_4 \leq n$ þannig að $\pi _{i_1} < \pi _{i_3} < \pi _{i_2} < \pi _{i_4}$ með bili milli talna. Ef til er fleiri en ein fernd af slíkum vísum má prenta hverja sem er þeirra.

Stigagjöf

4
4
1 2 3 4
4
1 3 2 4
10
3 4 2 5 1 6 7 8 10 9
10
8 5 7 2 9 6 3 4 1 10

Ekkert mynstur!
1 2 3 4
Ekkert mynstur!
2 3 6 10