One-Dimensional Battle Ships
Contest: Codeforces Round #Pi (Div. 2)
Difficulty rating: 1700
Tags: binary search, data structures, greedy, sortings

Alice and Bob love playing one-dimensional battle ships. They play on the field in the form of a line consisting of n square cells (that is, on a 1 × n table).

At the beginning of the game Alice puts k ships on the field without telling their positions to Bob. Each ship looks as a 1 × a rectangle (that is, it occupies a sequence of a consecutive squares of the field). The ships cannot intersect and even touch each other.

After that Bob makes a sequence of "shots". He names cells of the field and Alice either says that the cell is empty ("miss"), or that the cell belongs to some ship ("hit").

But here's the problem! Alice like to cheat. May be that is why she responds to each Bob's move with a "miss".

Help Bob catch Alice cheating — find Bob's first move, such that after it you can be sure that Alice cheated.

Input format:
The first line of the input contains three integers: n, k and a (1 ≤ n, k, a ≤ 2·105) — the size of the field, the number of the ships and the size of each ship. It is guaranteed that the n, k and a are such that you can put k ships of size a on the field, so that no two ships intersect or touch each other.

The second line contains integer m (1 ≤ m ≤ n) — the number of Bob's moves.

The third line contains m distinct integers x1, x2, ..., xm, where xi is the number of the cell where Bob made the i-th shot. The cells are numbered from left to right from 1 to n.

Output format:
Print a single integer — the number of such Bob's first move, after which you can be sure that Alice lied. Bob's moves are numbered from 1 to m in the order the were made. If the sought move doesn't exist, then print "-1".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
11 3 3
5
4 8 6 1 11

Example output:
3

Example input:
5 1 3
2
1 5

Example output:
-1

Editorial:
First, we should understand when the game ends. It will happen when on the n-sized board it will be impossible to place k ships of size a. For segment with length len we could count the maximum number of ships with size a that could be placed on it. Each ship occupies a + 1 cells, except the last ship. Thus, for segment with length len the formula will look like $$\frac{len+1}{a+1}$$ (we add "fictive" cell to len cells to consider the last ship cell). This way, for [l..r] segment the formula should be $${ \frac { r - l + 2 } { a + 1 } }$$.
For solving the problem we should store all the [l..r] segments which has no "free" cells (none of them was shooted). One could use (std: : set) for that purpose. This way, before the shooting, there will be only one segment [1..n]. Also we will store current maximum number of ships we could place on a board. Before the shooting it is equal to $${ \frac { n + 1 } { a + 1 } }$$.
With every shoot in cell x we should find the segment containing shooted cell (let it be [l..r]), we should update segment set. First, we should delete [l..r] segment. It means we should decrease current maximum number of ships by $${ \frac { r - l + 2 } { a + 1 } }$$ and delete it from the set. Next, we need to add segments [l..x - 1] and [x + 1..r] to the set (they may not be correct, so you may need to add only one segments or do not add segments at all) and update the maximum number of ships properly. We should process shoots one by one, and when the maximum number of ships will become lesser than k, we must output the answer. If that never happen, output  - 1.