题目描述

爱丽丝和鲍勃喜欢玩一维舰队游戏。

在 \(1×n\) 的桌子上，爱丽丝将 \(k\) 艘一样的战舰放在桌上，每艘战舰会占据 \(1×a\) 的桌面，战舰不能相交，甚至不能相邻（即两艘战舰之间需要有一个单位的间距）

之后，鲍勃进行了一系列“射击”。爱丽丝要么说击中的单元格是空的（“\(miss\)”），要么说击中的单元格属于某艘船（“\(hit\)”）。

但问题来了！爱丽丝喜欢作弊。可能这就是为什么她对鲍勃的每一次“射击”都用“\(miss\)”来回应的原因。

帮助鲍勃揭发爱丽丝作弊，找出鲍勃在第几次“射击”后，桌面一定不能放置 \(k\) 艘战舰，这样鲍勃就可以确定爱丽丝作弊了。

格式

输入格式

第一行三个正整数，\(n、k、a(1≤n,k,a≤10^6)\)，表示左面的长度、桌面上放置的战舰数和战舰的长度。数据保证起初一定能将k艘战舰放在桌面上，且不相交和不相邻。

第二行包含整数 \(m(1≤m≤n)\)，表示鲍勃的射击次数。

第三行包含 \(m\) 个不同的整数 \(x_1,x_2,…,x_i,…,x_m\)，其中 \(x_i\) 表示鲍勃射击的单元格的位置。单元格从左到右从 \(1\) 到 \(n\) 编号。

输出格式

输出一个正整数，表示鲍勃的这一次射击之后，你就可以确定爱丽丝作弊了。鲍勃的射击动作顺序从 \(1\) 到 \(m\) 编号。如果所有的射击动作后都不能确定爱丽丝作弊了，则打印“ \(-1\) ”。

样例1

样例输入1

11 3 3
5
4 8 6 1 11

样例输出1

3

限制

时间：\(1s\) 空间：\(256M\)

对于 \(20\%\) 的数据：\(1≤n,k,a≤100\)；

对于 \(40\%\) 的数据：\(1≤n,k,a≤5000\)；

对于 \(100\%\) 的数据：\(1≤n,k,a≤10^6\)；

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛 \(T2\)