시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 33 6 5 19.231%

문제

영선이와 효빈이는 평소 전함게임을 즐겨한다. 전함게임은 n칸이 일렬로 놓여진 게임판에서 즐길 수 있는데, 공격과 수비로 역할이 나뉜다.

우선 수비는 전함 k개를 게임판 위에 배치하는데, 이때 전함끼리 겹치거나 맞닿아 있으면 안된다. 전함은 일렬로 a칸을 차지한다. 그리고 전함의 위치는 공격은 볼 수가 없다.

전함이 다 배치되면 공격은 m번의 미사일을 발사하는데, 미사일들을 통해 하나의 전함이라도 맞춘다면 게임에서 이긴다. 이 미사일은 게임판의 한 칸을 공격한다.

이제 게임을 시작한다!!

영선이가 공격을, 효빈이가 수비를 한다. 근데 효빈이는 이 게임에서 지기 싫어 결국 거짓말을 치기로 했다. 공격입장에서 전함의 위치는 볼 수 없기 때문에, 전함에 미사일이 맞아도 안 맞았다고 말한다. 하지만 꼬리가 길면 밟히기 때문에, 논리적으로 봤을 때 전함을 어떻게든 배치하였더라도 미사일을 맞게 된다면, 패배를 인정할 것이다.

영선이는 거짓말을 친 사실을 알면 매우 화를 낼 것이므로, 효빈이는 몇 번째 미사일에서부터 어떻게 배치하더라도 전함이 미사일을 맞게 되는지를 알고 싶다.

효빈이를 대신하여, 몇번째 미사일에서 패배를 인정하면 되는지 출력하시오. 만약 마지막 미사일까지 전부 피해 이길 수 있다면 -1을 출력하시오.

입력

첫째 줄에는 게임판의 칸 수 n, 전함의 개수 k, 전함이 차지하는 칸 수a가 주어진다.(1≤n,k,a≤200,000)

둘째 줄에는 영선이가 쏠 수 있는 미사일의 개수 m이 주어지고,(1≤m≤n)

셋째 줄에는 영선이가 쏠 예정인 미사일의 위치가 서로 다른 정수 m개가 주어진다. 게임판의 위치는 1부터 n까지 순서대로 매겨져 있다. 또한, 조건에 맞게 전함을 게임판에 배치할 수 있게 k와 a가 주어짐이 보장된다.

출력

효빈이가 몇번째 미사일까지 공격당할 시 패배를 인정하면 되는지 출력하시오. 만약 전부 피할 수 있다면 -1을 출력하시오.

예제 입력 1

11 3 3
5
4 8 6 1 11

예제 출력 1

3

예제 입력 2

5 1 3
2
1 5

예제 출력 2

-1