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