Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

As a prize for the qualifiers to the regional round of informatics competitions, the Commitee gives you a \(Q\) arrays of integers. These arrays are extracted from a main array \(A\) of length \(N\) by extracting a contiguous subarray. More precisely, the \(i\)-th subarray is determined by the values \(l_i\) and \(r_i\), meaning that it contains elements \(A_{l_i}, A_{l_i+1}, ..., A_{r_i}\), in that order.

However, you are not very fond of this gift, since you only like the arrays which are already sorted in a non-decreasing order. Hence, you decided to alter your arrays slightly. Since you do not want to be ungrateful, you will alter your arrays by deleting at most one element from every array. Since you are also too lazy to actually change all these arrays, it suffices to determine for each one whether it is possible to sort it by removing at most one element.

During this process, we assume that deleting an element from one of the arrays has no effect on other arrays.

Input format

The first line of the standard input contains a positive integer \(N\), the number of elements in the main array.

The second line contains \(N\) integers, \(A_1, A_2, ..., A_N\), which represent the elements of main array.

The third line contains a positive integer \(Q\), the number of arrays you received.

Each of the next \(Q\) lines contains two indices, \(l_i\) and \(r_i\), denoting the beginning and the end of \(i\)-th array. More precisely, the \(i\)-th array contains the elements \({A_{l_i}, A_{l_i+1}, ... , A_{r_i}}\) in this order.

Output format

Your program should print \(Q\) lines to the standard ouptput. In the \(i\)-th line, you need to print “DA” (no quotation marks) if it is possible to sort the \(i\)-th array by deleting at most one element, and “NE” (no quotation marks) otherwise.

Sample testcase


1 7 2 7 2 2 3
1 4
2 7
4 6
5 5




The first array is \([A_1, A_2, A_3, A_4]\), i.e. \([1, 7, 2, 7]\). By deleting the second element, we obtain a sorted array \([1, 2, 7]\).

The second array is \([A_2, A_3, A_4, A_5, A_6, A_7]\), i.e. \([7, 2, 7, 2, 2, 3]\). It is not hard to see that one cannot make this array sorted by deleting one element.

The third array is \([A_4, A_5, A_6]\), i.e. \([7, 2, 2]\). By deleting the first element, we obtain a sorted array \([2, 2]\).

The fourth array is \([A_5]\), i.e. \([2]\). This array is sorted already, so there is nothing to do.


The test cases are split into five disjoint groups:


An array \([B_1, B_2, B_3, ... , B_M]\) is sorted in a non-decreasing order if and only if we have \(B_1 \leq B_2 \leq ... \leq B_M\).