URI Online Judge | 1740

Is it Ordered?

By Paulo Cezar Pereira Costa BR Brazil

Timelimit: 4

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:

Input

There might be several test cases. The first line of each test case begins with an integer 1 ≤ N ≤ 104, the amount of numbers on the initial sequence. On the next line there are N integers |A[i]| ≤ 109 (1 ≤ i ≤ N). The next line contains an integer 1 ≤ Q ≤ 105, 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