In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #12 exercise sheet]

[AED072] Is this a Heap?

Sam has just learned about heaps at his data structures and algorithms class. He knows that a max heap is a complete binary tree in which each node is greater than or equal to its children. The following figure illustrates one heap and two trees that are not heaps:

Sam also learned that the easiest and most compact way to represented a heap is to use an array that implicitly represents the tree:

• The elements appear in the array in breadth-first order (from top to bottom, left to right).
• If we place the root at position 1, then:
  • The children of the node at position i are at positions i*2 and i*2+1
  • The parent of the node at position i is at position i/2 (integer division)

The following figure shows how an example heap would be represented as an array:

Sam was really fascinated with heaps and he learned that besides max heaps, there is also the notion of a min heap, which is similar to a max heap, with the exception that now each node should be smaller than or equal to its children.

Now, Sam is really curious to see if given any array he can find if it represented a min or max heap. Can you help him?

The Problem

Given a list of integer arrays, your task is to see if each of them represented a max heap, a min heap or neither.

Input

The first line of input contains an integer N, indicating the number of arrays to consider.

The following N lines each describe one array, each one starting with an integer L representing the length of the array, followed by L integers X₁, X₂, ..., X_L, the values of the array.

Output

The output should contain N lines, one for each array, with the string:

• "max heap" if the array represents a max heap
• "min heap" if the array represents a min heap
• "max or min heap" if the array could represent a min or max heap
• "none" if the array is not a max or min heap

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

6
10 12 10 8 7 5 4 6 1 3 2
10 11 10 12 7 5 4 6 1 3 2
10 12 10 8 7 2 4 6 1 3 5
7 8 5 6 5 4 1 6
3 1 3 2
3 2 2 2

max heap
none
none
max heap
min heap
max or min heap

Explanation of Example Input 1

The 6 arrays of the input correspond to the following 6 binary trees: