Hide

Problem A
Av(1324)

Languages en is

Five problems ready, and already Arnar and Atli are running out of ideas. In desperation they start asking other members of the faculty at RU what problems they should pose for their students, and after a bit of searching they end up talking to Henning. He says that “Pattern avoiding permutations” are what they’re looking for. He says that there is nothing more interesting than solving the problem of how many permutations avoid the pattern 1324. “Isn’t this a bit tough for the students? This is an unsolved problem!” Arnar says. After a bit of discussion a conclusion was reached, instead of having the students solve this unsolved problem, they only have to check whether a particular permutation avoids the pattern.

That is where you come in! The input gives you a permutation π1,π2,,πn of the numbers 1,2,,n. This means the numbers π1,π2,,πn are the numbers 1,2,,n, just possibly in a different order. Determining whether the pattern 1324 appears is achieved by checking whether there exist indices 1i1<i2<i3<i4n such that πi1<πi3<πi2<πi4.

Input

The first line of the input contains an integer 1q105, the number of permutations in the input. Next there are 2q lines, each two lines giving one permutation. The first of the two lines contains a single integer ni, the size of the permutation. The second contains the permutation 1π1,π2,,πnni, with the numbers separated by spaces. Let n be the sum of the sizes of all the permutations in the input. It is guaranteed that n106.

Output

For each permutation in the input, print a single line. If the pattern does not appear, print "Ekkert mynstur!". Otherwise print indices 1i1<i2<i3<i4n such that πi1<πi3<πi2<πi4, separating the indices by spaces. If there are several such sets of indices, any one of them will be accepted.

Scoring

Group

Points

Constraints

1

20

1ni4

2

20

1ni20

3

25

1ni60

4

25

1ni2000

5

10

1ni106

Sample Input 1 Sample Output 1
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
Hide

Please log in to submit a solution to this problem

Log in