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

Као награду за пролаз на окружно такмичење, комисија Вам поклања \(Q\) низова. Сваки од низова је добијен тако што је од главног низа \(A\), дужине \(N\), копиран неки узастопни подниз. Прецизније, \(i\)-ти низ је одређен вредностима \(l_i\) и \(r_i\), што значи да он садржи елементе \({A_{l_i}, A_{l_i+1}, ... , A_{r_i}}\), у том редоследу.

Вама се, међутим, овај поклон не свиђа много, јер Ви волите само низове који су сортирани у неопадајућем поретку. Зато ћете мало изменити низове које сте добили. Пошто не желите да испаднете незахвални, нећете их много мењати, па ћете из сваког низа избрисати највише један елемент. Такође, пошто Вас ипак мрзи да сада мењате толики број низова, довољно је да за сваки од њих само одредите да ли га је уопште могуће изменити да постане сортиран.

Подразумева се да брисање елемента из једног низа не утиче на друге низове.


Опис улаза


Први ред стандардног улаза садржи цео број \(N\), број елемената главног низа.

Други ред садржи \(N\) целих бројева који представљају главни низ \(A_1, A_2, ..., A_N\).

Трећи ред садржи цео број \(Q\), број поклоњених низова.

Наредних \(Q\) редова садрже по два броја, \(l_i, r_i\), који означавају да \(i\)-ти низ садржи елементе \({A_{l_i}, A_{l_i+1}, ... , A_{r_i}}\), у том редоследу.


Опис излаза


На стандардни излаз је потребно исписати \(Q\) линија - у \(i\)-тој линији исписати “DA” (без наводника) ако је \(i\)-ти низ могуће сортирати брисањем највише једног елемента, у супротном исписати “NE” (без наводника).


Пример


Улаз


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


Излаз


DA
NE
DA
DA


Објашњење


Први низ је \([A_1, A_2, A_3, A_4]\), тј. \([1, 7, 2, 7]\). Из њега можемо избрисати други елемент да бисмо добили низ \([1, 2, 7]\).

Други низ је \([A_2, A_3, A_4, A_5, A_6, A_7]\), тј. \([7, 2, 7, 2, 2, 3]\). Може се видети да који год елемент избришемо, низ неће бити сортиран.

Трећи низ је \([A_4, A_5, A_6]\), тј. \([7, 2, 2]\). Из њега можемо избрисати први елемент да бисмо добили низ \([2, 2]\).

Четврти низ је \([A_5]\), тј. \([2]\). Он је већ сортиран, па не морамо радити ништа.


Ограничења



Тест примери су подељени у пет дисјунктних група:



Напомена


Низ \([B_1, B_2, B_3, ... , B_M]\) је сортиран у неопадајућем поретку ако и само ако важи \(B_1 \leq B_2 \leq ... \leq B_M\).