#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> niz(300000,300000);
vector<int> stablo(560000,0);

void stablanje(int i,int gor,int n){//
    //cout << "ovo jebenoo sranjeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee        ";
    if(i*2<gor){
        stablanje(i*2,gor,n);
        stablanje(i*2+1,gor,n);
        int gran=i*2+1;
        while(gran<n){
            gran*=2;
        }
        gran=gran-n;
        if(stablo[i*2]+stablo[i*2+1]>1){
            stablo[i]=2;
        }
        else if(stablo[i*2+1]==1){// right side is wrong
            if(niz[gran-1]<=niz[gran] &&(niz[gran]<=niz[gran+1] ||(niz[gran]<=niz[gran+2] || niz[gran-1]<=niz[gran+1]))){
                stablo[i]=1;
            }
            else
                stablo[i]=2;
        }
        else if(stablo[i*2]==1){// left side is wrong
            if(niz[gran-1]<=niz[gran] &&(niz[gran-2]<=niz[gran-1] ||(niz[gran-3]<=niz[gran-1] || niz[gran-2]<=niz[gran]))){
                stablo[i]=1;
            }
            else
                stablo[i]=2;
        }
        else{
            if(niz[gran-1]<=niz[gran])
                stablo[i]=0;
            else if(niz[gran-1]<=niz[gran+1] || niz[gran-2]<=niz[gran])
                stablo[i]=1;
            else
                stablo[i]=2;
        }
    }
    else if(i<gor){
        stablanje(i*2,gor,n);
        stablanje(i*2+1,gor,n);
        int gran=(i*2+1)*2;
        if(niz[gran-1]<=niz[gran] && stablo[i*2]==0 && stablo[i*2+1]==0)
            stablo[i]=0;
        else if((niz[gran-1]<=niz[gran] || niz[gran-2]<=niz[gran]) && stablo[i*2]==1)
            stablo[i]=1;
        else if((niz[gran-1]<=niz[gran+1] || niz[gran-1]<=niz[gran+2]) && stablo[i*2+1]==1)
            stablo[i]=1;
        else
            stablo[i]=2;
        stablo[i]+=stablo[i*2]+stablo[i*2+1];
    }
    else{
        if(niz[i*2-n]<=niz[i*2+1-n])
            stablo[i]=0;
        else
            stablo[i]=1;
    }
}

int suma;

void sranjezvanosabiranje(int gor,int l,int d,int ciklus){// ovde mi je gor n
    if(l==d){
        suma+=stablo[l];
        return;
    }
    else if(l%2==1){
        int gran=l+1;
        while(gran<gor)
            gran*=2;
        gran-=gor;
        suma+=stablo[l];
        if(stablo[l]+stablo[l+1]>=2)
            return;
        if(stablo[l]==1 && ciklus==1){
            if(niz[gran-2]>niz[gran] && niz[gran-1]>niz[gran]){
                suma+=2;
            }
        }
        else if(stablo[l+1]==1 && ciklus==1){
            if(niz[gran-1]>niz[gran+1] && niz[gran-1]>niz[gran]){
                suma+=2;
            }
        }
        else if(stablo[l]+stablo[l+1]==1){
            if(niz[gran-1]<=niz[gran] &&(niz[gran]<=niz[gran+1] ||(niz[gran]<=niz[gran+2] || niz[gran-1]<=niz[gran+1]))){
                suma+=0;
            }
            else
                suma+=2;
            if(niz[gran-1]<=niz[gran] &&(niz[gran-2]<=niz[gran-1] ||(niz[gran-3]<=niz[gran-1] || niz[gran-2]<=niz[gran]))){
                suma+=0;
            }
            else
                suma+=2;
        }
        else{
            if(niz[gran-1]<=niz[gran])
                suma+=0;
            else if(niz[gran-1]<=niz[gran+1] || niz[gran-2]<=niz[gran])
                suma+=1;
            else
                suma+=2;
        }
        l++;
    }
    else if(d%2==0){// so we begin here on our exploration
        int gran=d;
        while(gran<gor)
            gran*=2;
        gran-=gor;
        suma+=stablo[d];
        if(stablo[d]+stablo[d-1]>=2)
            return;
        if(stablo[d]==1 && ciklus==1){
            if(niz[gran-2]>niz[gran] && niz[gran-1]>niz[gran]){
                suma+=2;
            }
        }
        else if(stablo[d-1]==1 && ciklus==1){
            if(niz[gran-1]>niz[gran+1] && niz[gran-1]>niz[gran]){
                suma+=2;
            }
        }
        else if(stablo[d]+stablo[d-1]==1){
            if(niz[gran-1]<=niz[gran] &&(niz[gran]<=niz[gran+1] ||(niz[gran]<=niz[gran+2] || niz[gran-1]<=niz[gran+1]))){
                suma+=0;
            }
            else
                suma+=2;
            if(niz[gran-1]<=niz[gran] &&(niz[gran-2]<=niz[gran-1] ||(niz[gran-3]<=niz[gran-1] || niz[gran-2]<=niz[gran]))){
                suma+=0;
            }
            else
                suma+=2;
        }
        else{
            if(niz[gran-1]<=niz[gran])
                suma+=0;
            else if(niz[gran-1]<=niz[gran+1] || niz[gran-2]<=niz[gran])
                suma+=1;
            else
                suma+=2;
        }
        d--;
    }
    if(suma>=2){
        return;
    }
    sranjezvanosabiranje(gor,l/2,d/2,ciklus++);
}

int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> niz[i];
    }
    int pom=1;
    while(pom<=n){
        pom*=2;
    }
    stablanje(1,pom/4,pom/2);
    int q,l,d;
    cin >> q;
    for(int i=0;i<q;i++){
        suma=0;
        cin >> l >> d;
        sranjezvanosabiranje(pom/2,l+pom/2-1,d+pom/2-1,0);
        if(suma>1)
            cout << "NE" << endl;
        else
            cout << "DA" << endl;
    }
    cout << endl;
    for(int i=1;i<=pom;i++){
        cout << stablo[i] << "  ";
    }
    //cout << "Hello world!" << endl;
    return 0;
}