CF567D.One-Dimensional Battle Ships

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.

爱丽丝和鲍勃喜欢玩一维战舰游戏。他们在一条由 $n$ 个方格组成的直线形棋盘（即一个 $1 \times n$ 的表格）上进行游戏。

游戏开始时，爱丽丝在棋盘上放置 $k$ 艘战舰，但不向鲍勃透露它们的具体位置。每艘战舰形如一个 $1 \times a$ 的矩形（即占据棋盘上连续的 $a$ 个方格）。战舰之间既不能相交，也不能彼此相邻（即不能“接触”）。

之后，鲍勃进行一系列“射击”。他报出棋盘上的某个方格，爱丽丝则回应该方格是“空的”（“未击中”），还是属于某艘战舰（“击中”）。

但问题来了！爱丽丝喜欢作弊。也许正因如此，她对鲍勃的每一次射击都回答“未击中”。

请帮助鲍勃揭穿爱丽丝的作弊行为——找出鲍勃的第几次射击，使得在该次射击之后，我们便能确定爱丽丝在说谎。

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 _x_1, _x_2, ..., x__m, where x__i 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.

输入的第一行包含三个整数：$n$、$k$ 和 $a$（$1 ≤ n, k, a ≤ 2·10^5$）——分别表示棋盘大小、战舰数量以及每艘战舰的长度。题目保证给定的 $n$、$k$ 和 $a$ 满足：可以在棋盘上放置 $k$ 艘长度为 $a$ 的战舰，使得任意两艘战舰互不相交且互不接触。

第二行包含一个整数 $m$（$1 ≤ m ≤ n$）——表示 Bob 的射击次数。

第三行包含 $m$ 个互不相同的整数 $x_1,\,x_2,\,...,\,x_m$，其中 $x_i$ 表示 Bob 第 $i$ 次射击所击中的格子编号。格子从左至右依次编号为 $1$ 到 $n$。

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".

输出一个整数——即满足条件的鲍勃第一步操作的编号个数，使得在此操作之后你能确定爱丽丝说了谎。鲍勃的操作按执行顺序从 1 到 $m$ 编号。如果不存在满足条件的操作，则输出 -1。