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
// Example program
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void testcase(int t) {
  int n, k;
  cin >> n >> k;
  vector <int> A(n+1);
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
  }
  if (k == 1) {
    cout << "NIE" <<endl;
    return;
  }
  if (k >= 4) {
    for (int i = 1; i < n; i++) {
      if (A[i] >= A[i+1]) {
        cout << "TAK" <<endl;
        int j = max(1, min(i+1,n-1)-(k-1)+1);
        for (int d = 0; d < k-1; d++) {
          cout << j+d << " ";
        }
        cout <<endl;
        return;
      }
    }
    cout << "NIE" <<endl;
    return;
  }

  int INF = (1<<30);
  vector <int> Min_pref(n+2, INF), Max_suf(n+2, -INF);
  for (int i = 1; i <= n; i++) {
    Min_pref[i] = min(Min_pref[i-1], A[i]);
  }
  for (int i = n; i >= 1; i--) {
    Max_suf[i] = max(Max_suf[i+1], A[i]);
  }
  
  if (k == 2) {
    for (int i = 1; i < n; i++) {
      if (Min_pref[i] >= Max_suf[i+1]) {
        cout << "TAK" <<endl;
        cout << i <<endl;
        return;
      }
    }
    cout << "NIE" <<endl;
    return;
  }

  if (k == 3) {
    if (A[1] >= A[n]) {
      cout << "TAK" <<endl;
      cout << 1 << " " << n-1 <<endl;
      return;
    }

    int min_v = A[1], min_v_max_ind = 1;
    for (int i = 2; i <= n; i++) {
      if (min_v >= A[i]) {
        min_v = A[i];
        min_v_max_ind = i;
      }
    }

    if (min_v_max_ind > 1) {
      cout << "TAK" <<endl;
      cout << min_v_max_ind-1 << " " << min_v_max_ind <<endl;
      return;
    }
    
    int max_v = A[n], max_v_min_ind = n;
    for (int i = n-1; i >= 1; i--) {
      if (max_v <= A[i]) {
        max_v = A[i];
        max_v_min_ind = i;
      }
    }

    if (max_v_min_ind < n) {
      cout << "TAK" <<endl;
      cout << max_v_min_ind-1 << " " << max_v_min_ind <<endl;
      return;
    }

    cout << "NIE" <<endl;
    return;
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; t++) {
    testcase(t);
  }
  return 0;
}