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
#include <iostream>

using namespace std;
int const s=1<<19;
int tab[s*2];
int tab2[2*s];
int r=-1;
void upd(int v){
    while(v>=1){
    tab[v]=min(tab[v*2],tab[v*2+1]);v/=2;}
    return;
}
void upd2(int v){
    while(v>=1){
    tab2[v]=max(tab2[v*2],tab2[v*2+1]);v/=2;}
    return;
}
int que(int a,int b){
    int wynik=tab[a];
    while(a<=b){
        if(a%2==1){wynik=min(wynik,tab[a]);a++;}
        if(b%2==0){wynik=min(wynik,tab[b]);b--;}
        a/=2;
        b/=2;
    }
    return wynik;
}
int que2(int a,int b){
    int wynik=tab2[a];
    while(a<=b){
        if(a%2==1){wynik=max(wynik,tab2[a]);a++;}
        if(b%2==0){wynik=max(wynik,tab2[b]);b--;}
        a/=2;
        b/=2;
    }
    return wynik;
}
int main()
{
    int n,k;
    cin>>n>>k;
    pair<int,int>ma={0,0};
    pair<int,int>mi={1e9,0};
    for(int i=0;i<n;i++){
        cin>>tab[i+s];
        if(i>0){if(tab[i+s]<=tab[i+s-1]){r=i;}}
        tab2[i+s]=tab[i+s];
        upd((i+s)/2);
        upd2((i+s)/2);
        if(tab[i+s]<=mi.first){
            mi={tab[i+s],i};
        }
        if(tab[i+s]>ma.first){
            ma={tab[i+s],i};
        }
    }
    k--;
    if(k==1){
        for(int i=0;i<n;i++){
        if(i==n-1){cout<<"NIE";break;}
        if(que(s,s+i)>=que2(s+i+1,s+n-1)){
            cout<<i+1;break;
        }}
    }
    if(k==2){
        if(mi.second==0){
        if(ma.second==n-1){
            cout<<"NIE";
        }else{
            if(ma.second==0){ma.second=1;}
        cout<<ma.second-1<<" "<<ma.second;
        }}else{
        cout<<mi.second-1<<" "<<mi.second;
        }
    }
    if(r==n-1){r=n-2;}
    if(k>=3){
        if(r==-1){cout<<"NIE";return 0;}
        for(int i=1;k>3;i++){
            cout<<i<<" ";
            k--;
            if(r-1==i){
                while(k>0){i++;cout<<i<<" ";k--;}
            }
        }
        if(k==0){return 0;}
        cout<<r<<" "<<r+1<<" "<<r+2;
    }
    return 0;
}