https://cs.stackexchange.com/questions/3078/algorithm-that-finds-the-number-of-simple-paths-from-s-to-t-in-g


/* WWI 2017 konkurs kwalifikacyjny zadanie zapałki grupa 3 Anita Śledź */
#include<iostream>
using namespace std;

const int N = 1000 * 1000 + 7;
const int N2 = (1 << 20) + 10;

int n, m, baza;

int najw[N2];
long long int sum[N2];

int baz(int a){ //funkcja licząca mi bazę dla danego a
    int wyn = 1;
    while (wyn <= a){
        wyn = wyn * 2;
    }
    return wyn;
}


void wstaw(int co, int gdzie){
    gdzie = gdzie + baza;
    sum[gdzie] = co;
    najw[gdzie] = co;
    gdzie = gdzie/2;
    while( gdzie >= 1){
        sum[gdzie] = sum[2 * gdzie] + sum[2 * gdzie + 1];
        najw[gdzie] = max( najw[gdzie * 2], najw[gdzie * 2 + 1] );
        gdzie = gdzie/2;
    }
}

long long int sumy(int pzap, int kzap, int v, int pjest, int kjest){
    if(kjest < pzap || kzap < pjest){
        return 0;
    }
    if(kjest <= kzap && pzap <= pjest){
        return sum[v];
    }
    int mid = (pjest + kjest) / 2;
    return(sumy(pzap, kzap, v*2, pjest, mid) + sumy(pzap, kzap, v*2+1, mid+1, kjest));
}


long long int maksy(int pzap, int kzap, int v, int pjest, int kjest){ // początek zapytania, koniec zapytania, aktualny wierzchołek, początek rozpatrywanego przedziału, koniec rozpatrywanego przedziału
    if(kjest < pzap || kzap < pjest){
        return 0;
    }
    if(kjest <= kzap && pzap <= pjest){
        return najw[v];
    }
    int mid = (pjest + kjest) / 2;
    return max(maksy(pzap, kzap, v*2, pjest, mid), maksy(pzap, kzap, v*2+1, mid+1, kjest));
}


int main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    baza = baz(n);
    for(int i = 0; i < n; i++){
        int pom;
        cin >> pom;
        wstaw(pom, i);
    }
   // for(int i = 0; i < 2*baza; i++){
     //   cout << najw[i] << " ";
   // }

 //   cout << "\n";
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        long long int wszystkie = sumy(a, b, 1, 0, baza-1);
        int najwieksza = maksy(a, b, 1, 0, baza-1);

        if((b-a > 1) && (2 * najwieksza < wszystkie)){
            cout << "TAK\n";
        }
        else{
            cout<< "NIE\n";
        }
       // cout << maksy(a, b, 1, 0, baza-1) << " " << sumy(a, b, 1, 0, baza-1) << "\n";

    }


    return 0;
}