# CFR 567 D. One-Dimensional Battle Ships ( Sqrt Decomposition )

Problem - 567D - Codeforces

N ≤ 2e5
M ≤ 2e5

O( N ^ 1.5 ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;
const int BS = 500;

int N, K, A;
int blk_l[ BS ], blk_r[ BS ];
int mark[ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> K >> A;
int M; cin >> M;
int sum = ( N + 1 ) / ( A + 1 );
if( sum < K ){
cout << -1 << endl;
exit( 0 );
}
for( int i = 0; i < BS; ++i ){
blk_l[ i ] = -1;
blk_r[ i ] = N;
}
for( int qi = 0; qi < M; ++qi ){
int u; cin >> u; --u;
int L = -1, R = N; // [ L, R ]
for( int i = u - 1; ( i + BS ) % BS != BS - 1; --i ){
if( mark[ i ] ){
L = i;
break;
}
}
for( int i = u / BS - 1; L == -1 and i >= 0; --i ){
L = blk_l[ i ];
}
for( int i = u + 1; i % BS != 0; ++i ){
if( mark[ i ] ){
R = i;
break;
}
}
for( int i = u / BS + 1; R == N and i < BS; ++i ){
R = blk_r[ i ];
}
sum = sum - ( R - L ) / ( A + 1 ) + ( u - L ) / ( A + 1 ) + ( R - u ) / ( A + 1 );
mark[ u ] = 1;
blk_l[ u / BS ] = max( blk_l[ u / BS ], u );
blk_r[ u / BS ] = min( blk_r[ u / BS ], u );
if( sum < K ){
cout << qi + 1 << endl;
exit( 0 );
}
}
cout << -1 << endl;
return 0;
}