← 返回题目列表

Codeforces · 567/D

D. 一维战舰

中文机器翻译题面 查看原题

Alice 和 Bob 喜欢玩一维战舰。他们在球场上以由 n 个方格组成的线的形式(即在 1 × n 的桌子上)进行比赛。

在游戏开始时,爱丽丝将 k 艘船放置在战场上,但没有告诉鲍勃它们的位置。每艘船看起来都是一个 1 × 矩形(也就是说,它占据了一系列连续的正方形区域)。船只不能相交,甚至不能互相接触。

之后鲍勃进行了一系列“射击”。他命名了该字段的单元格,爱丽丝要么说该单元格是空的(“未命中”),要么说该单元格属于某艘船(“命中”)。

但这就是问题!爱丽丝喜欢作弊。可能这就是为什么她对鲍勃的每次举动都回应“未命中”。

帮助鲍勃发现爱丽丝作弊——找到鲍勃的第一步,这样你就可以确定爱丽丝作弊了。

输入

输入的第一行包含三个整数:n、k 和 a (1 ≤ n, k, a ≤ 2·105) — 字段的大小、船只的数量和每艘船只的大小。保证 n、k 和 a 使得您可以将 k 艘大小为 a 的船只放置在场地上,从而不会有两艘船只相交或相互接触。

第二行包含整数 m (1 ≤ m ≤ n) — Bob 的移动次数。

第三行包含 m 个不同的整数 x1, x2, ..., xm,其中 xi 是 Bob 进行第 i 次射击的单元格编号。单元格从左到右编号为 1 到 n。

输出

打印一个整数——鲍勃第一次移动的次数,之后你就可以确定爱丽丝撒谎了。 Bob 的动作按照动作的顺序从 1 到 m 进行编号。如果寻找的移动不存在,则打印“-1”。

示例

输入 #1

11 3 3
5
4 8 6 1 11

输出 #1

3

输入 #2

5 1 3
2
1 5

输出 #2

-1

输入 #3

5 1 3
1
3

输出 #3

1