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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<cstdio>
#include<algorithm>
using namespace std;

#define N_MAX 500005

int n,k;
int input[N_MAX];
int maks_suf[N_MAX];
int maks_suf_pos[N_MAX];
int mini_pref[N_MAX];
int mini_pref_pos[N_MAX];

int main()
{
  scanf("%d %d", &n, &k);
  for(int i=0;i<n;i++) {
    scanf("%d", input+i);
  }
  int res=0;
  if(k>=4) {
    res=-1;
    for(int i=1;i<n;i++) {
      if(input[i]<=input[i-1]) {
        res=i;
        break;
      }
    }
    if(res==-1) {
      printf("NIE\n");
    } else {
      printf("TAK\n");
      k-=4;
      int tmpk=0;
      int deb;
      //scanf("%d", &deb);
      while(k>0 && tmpk<res-2) {
        printf("%d ",++tmpk);
        k--;
        //printf("\n next: ");
        //scanf("%d", &deb);
      }
      printf("%d %d %d ", res-1, res, res+1);
        //printf("\n next: ");
        //scanf("%d", &deb);
      tmpk=res+1;
      while(k>0) {
        printf("%d ", ++tmpk);
        k--;
        //printf("\n next: ");
        //scanf("%d", &deb);
      }
      printf("\n");
    }
  } else {
    //pref i suf
    //minima pref
    mini_pref[0]=input[0];
    mini_pref_pos[0]=0;
    int mini_tmp=input[0];
    int mini_tmp_pos=0;
    maks_suf[n-1]=input[n-1];
    maks_suf_pos[n-1]=n-1;
    int maks_tmp=input[n-1];
    int maks_tmp_pos=n-1;
    for(int i=1;i<n;i++) {
      if(input[i]<=mini_tmp) {
        mini_tmp=input[i];
        mini_tmp_pos=i;
      }
      mini_pref[i]=mini_tmp;
      mini_pref_pos[i]=mini_tmp_pos;
      if(input[n-i-1]>=maks_tmp){
        maks_tmp=input[n-i-1];
        maks_tmp_pos=n-i-1;
      }
      maks_suf[n-i-1]=maks_tmp;
      maks_suf_pos[n-i-1]=maks_tmp_pos;
    }
    /*
    printf("Suf maks:\n");
    for(int i=0;i<n;i++) {
      printf("%d ", maks_suf[i]);
    }
    printf("\n");
    printf("Suf maks pos:\n");
    for(int i=0;i<n;i++) {
      printf("%d ", maks_suf_pos[i]);
    }
    printf("\n");
    printf("Pref mini:\n");
    for(int i=0;i<n;i++) {
      printf("%d ", mini_pref[i]);
    }
    printf("\n");
    printf("Pref mini pos:\n");
    for(int i=0;i<n;i++) {
      printf("%d ", mini_pref_pos[i]);
    }
    printf("\n");
    */
    if(k==2) {
      //jedno ciecie
      res=-1;
      for(int i=1;i<n;i++) {
        if(mini_pref[i-1]>=maks_suf[i]) {
          //printf("%d =>  min: %d, maks:%d\n", i, mini_pref[i-1], maks_suf[i]);
          res=i;
          break;
        }
      }
      if(res==-1) {
        printf("NIE\n");
      } else {
        printf("TAK\n");
        printf("%d\n",res);
      }
    } else {
      //dwa ciecia k=3
      res=-1;
      if(mini_pref_pos[n-1]!=0) {
        //mini
        printf("TAK\n");
        res = mini_pref_pos[n-1];
        if(res==n-1) {
          //min jest ostatnie
          printf("%d %d\n", n-2, n-1);
        } else {
          //min nie jest ostatnie ani pierwsze
          printf("%d %d\n", res,res+1);
        }
      } else {
        if(maks_suf_pos[0]!=n-1) {
          //maks
          printf("TAK\n");
          res = maks_suf_pos[0];
          if(res==0) {
            //maks na poczatku
            printf("1 2\n"); 
          } else {
            printf("%d %d\n", res, res+1);
          }
        } else {
          //albo jest drugie minimum albo drugie maksimum albo lipa
          res=-1;
          for(int i=1;i<n-1;i++) {
            //czy min na innej pozycji
            if(input[i]==input[0]) {
              res=i;
              break;
            }
            //czy maks na innej pozycji
            if(input[i]==input[n-1]) {
              res=i;
              break;
            }
          }
          if(res==-1) {
            printf("NIE\n");
          } else {
            printf("TAK\n");
            //wypisac ciecie na res
            printf("%d %d\n",res, res+1);
          }
        }
      }
    }
  }
  return 0;
}