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
108
109
110
#include <ios>
#include <algorithm>
#include <unordered_map>
using namespace std;
long long a,b,c,d,e,f,l,k,p,w,n,m,czy;
long long wej[500001],suf[500001],pref[500001],spl[500001];
long long srt[500001],ile[500001],pierw[500001],ost[500001];
long long z;
unordered_map <long long, long long> mapa;
inline void getnum(long long& r){
    z=getchar_unlocked();
    r=0;
    while (z<='9'&&z>='0'){
        r=r*10+z-'0';
        z=getchar_unlocked();
    }
}
int main(){
    getnum(n); getnum(m);
    //f=m;
    for (a=1; a<=n; ++a){
        getnum(wej[a]);
        srt[a]=wej[a];
    }
    sort(srt+1, srt+n+1);
    mapa.reserve(n);
    for (a=1; a<=n; ++a)
        if (srt[a]>p){
            mapa[srt[a]]=++l;
            p=srt[a];
            srt[a]=l;
        }
    for (a=1; a<=n; ++a){
        wej[a]=mapa[wej[a]];
        if (!ile[wej[a]]++)
            pierw[wej[a]]=a;
        ost[wej[a]]=a;
    }
    p=1; k=n;
    while (m>2){
        m-=2;
        if (srt[p]!=wej[p]||ile[srt[p]]>1){
            l=ost[srt[p]];
            if (l==k){
                spl[p]=1;
                spl[k-1]=1;
            }
            else
                spl[l]=spl[l-1]=1;
            czy=1;
            break;
        }
        if (srt[k]!=wej[k]||ile[srt[k]]>1){
            l=pierw[srt[k]];
            spl[l]=spl[l-1]=1;
            czy=1;
            break;
        }
        spl[p++]=1; spl[--k]=1; // spl[i] means i|i+1
    }
    if (czy)
        for (a=1; m>1&&a<=n; ++a){
            m-=spl[a]^1;
            spl[a]=1;
        }
    else if (m<2){
        printf("NIE");
        return 0;
    }
    if (m==2){
        pref[p-1]=1000000000;
        for (a=p; a<=k; ++a)
            pref[a]=min(pref[a-1], wej[a]);
        l=0;
        for (a=k; a>p; --a){
            l=max(l, wej[a]);
            if (pref[a-1]>=l){
                spl[a-1]=1;
                break;
            }
        }
        if (a==p){
            printf("NIE\n");
            return 0;
        }
    }
    printf("TAK\n");
    //return 0;
    //long long popmin=0,lmin=1000000000; czy=0;
    for (a=1; a<n; ++a){
        //if (wej[a]<lmin&&wej[a]>popmin)
        //    lmin=wej[a];
        if (spl[a]){
            ++w;
            printf("%lld ", a);
            //if (lmin==1000000000)
            //    czy=1;
            //popmin=lmin;
            //lmin=1000000000;
        }
    }
    /*if (lmin==1000000000)
        czy=1;
    if (!czy)
        return 44;
    if (w+1!=f){
        printf("----------------%lld!=%lld\n", w, f);
        return 69;
    }*/
}