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

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.

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.

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.

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

```
DA
NE
DA
DA
```

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.

- \(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:

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