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

Input

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

Output

DA
NE
DA
DA

Explanation

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.

Constraints

• \(1 \leq N \leq 2 \cdot 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq L_i \leq R_i \leq N\) for \(1 \leq i \leq Q\)
• \(1 \leq A_i \leq N\)

The test cases are split into five disjoint groups:

• In the test cases worth 15 points, we have additional constraints: \(N, Q \leq 200\).
• In the test cases worth 25 points, we have additional constraints: \(N, Q \leq 3000\).
• In the test cases worth 10 points, we have additional constraints: \(Q = 5\).
• In the test cases worth 20 points, we have additional constraints: all elements of the array are either \(1\) or \(2\).
• In the test cases worth 20 points, we have no additional constraints:
  

Remark

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\).