1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>

using namespace std;
int T[500100];
int Mi[500100];
int Ma[500100];
int St[500100];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    int mi=INT_MAX;
    for(int i=0;i<n;i++){
        cin>>T[i];
        mi = min(mi,T[i]);
        Mi[i]=mi;
    }
    int ma = -1;
    for(int i=n-1;i>=0;i--){
        ma=max(ma,T[i]);
        Ma[i]=ma;
    }
    if(k==2){
        for(int i=1;i<n;i++){
            if(Mi[i-1]>=Ma[i]){
                cout<<"TAK"<<"\n"<<i<<"\n";
                return 0;
            }
        }
        cout<<"NIE"<<"\n";
        return 0;
    }
    if(k==3){
    if(T[0]>=T[1]){
        cout<<"TAK"<<"\n";
        cout<<1<<" "<<2<<"\n";
        return 0;
    }
    if(T[n-1]<=T[n-2]){
        cout<<"TAK"<<"\n";
        cout<<n-1<<" "<<n<<"\n";
        return 0;
    }
    ma=-1;
    mi=INT_MAX;
    int poz2=0;
    int poz =0;
    for(int i=0;i<n;i++){
        if(T[i]>ma){
            ma=T[i];
            poz=i;
        }
        if(T[i]<=mi){
            mi=T[i];
            poz2=i;
        }

    }
    if(poz==n-1 and poz2==0){
        cout<<"NIE"<<"\n";
        return 0;

    }
    cout<<"TAK"<<"\n";
    if(poz2==0){
        cout<<poz<<" "<<poz+1<<"\n";
    }
    else{
        cout<<poz2<<" "<<poz2+1<<"\n";
    }
    return 0;
    }
    if(k>=4){
            k--;
        int pop=T[0];
        for(int i=1;i<n;i++){
            if(T[i]<=pop){
                cout<<"TAK"<<"\n";
                St[i+1]=1;
                k--;
                St[i]=1;
                k--;
                if(i!=1){
                    St[i-1]=1;
                    k--;
                }
                for(int j=0;j<n;j++){
                    if(k>0 and St[j]!=1){
                        St[j]=1;
                        k--;
                    }
                    if(St[j]==1){
                        cout<<j+1<<" ";
                    }
                }
                cout<<"\n";
                return 0;
            }
            pop=T[i];

        }
        cout<<"NIE"<<"\n";
        return 0;
    }
}