bee 1740 - Is it Ordered?

Chavaska likes to play with integer sequences. He has a sequence A consisting of N integers that he modifies and analyzes. Particularly he is interested in the ordering of some contiguous subsequences.

He explained to Kabralouco how he is having fun and invited him to play. Kabralouco wants to play but as he can’t think as fast as Chavaska and doesn’t like to stay behind, he decided to cheat and now asks your help creating a program capable of quickly dealing with the following operations:

0 X Y – Swap the elements at positions X and Y.
1 X Y – Change the value of element at position X to Y.
2 X Y – Insert element Y at position X.
3 X – Remove element at position X.
4 X Y – Query the ordering of the elements on (the subsequence) A[X...Y] and the answers must be:

“ALL EQUAL” – If A[i] = A[i+1] for all i in [X,Y −1]
“NON DECREASING” – If A[i] ≤ A[i+1] for all i in [X,Y−1] and A[i] ≠ A[i+1] for some i in [X,Y−1]
“NONINCREASING” – If A[i] ≥ A[i+1] for all i in [X,Y−1] and A[i] ≠ A[i+1] for some i in [X,Y−1]
“NONE” – If none of the above orderings happens.

Input

There might be several test cases. The first line of each test case begins with an integer 1 ≤ N ≤ 10⁴, the amount of numbers on the initial sequence. On the next line there are N integers |A[i]| ≤ 10⁹ (1 ≤ i ≤ N). The next line contains an integer 1 ≤ Q ≤ 10⁵, the number of operations that must be executed. The following Q lines are the operations.

Output

Your program should output one line for each query (“4 X Y”), answering whether the subsequence A[X...Y] is NON INCREASING, NON DECREASING, ALL EQUAL or NONE as explained above.

Sample Input	Sample Output
8 15 6 24 48 56 6 2 11 11 4 3 5 4 5 7 4 1 7 0 3 6 4 2 5 2 4 6 4 2 4 1 3 13 4 2 4 3 3 4 2 4	NON DECREASING NON INCREASING NONE NON DECREASING ALL EQUAL NONE NON DECREASING