꿈

면접 대비

시간 제한1초메모리 제한1024 MB

요약
악몽을 꾼 날마다 최근 K일의 꿈을 잊어버릴 때, N번째 날 이후 주어진 날짜 집합의 꿈만 정확히 기억되는지 판별한다.
난이도

보통10점 중 5점

유형
구간, 정렬, 구현, 수학
정답자
아직 제출이 없습니다

문제

쿠는 11번째 날부터 NN번째 날까지 매일 하나의 꿈을 꾼다. 하지만 악몽을 꾸면 충격을 받아서 최근에 꾼 꿈들을 잊어버린다.

ii번째 날에 악몽을 꾸면, KK일 전에 꾼 꿈부터 ii번째 날에 꾼 꿈까지 모두 잊어버린다. 구체적으로 max⁡(1,i−K),⋯ ,i−1,i\max(1, i-K), \cdots , i-1, i번째 날에 꾼 꿈들을 모두 잊어버린다. 이 중 이미 잊은 꿈이 있다면, 해당 꿈은 그대로 잊은 상태가 유지된다.

집합 S=S_1,S_2,...,S_MS = \\{S\_1, S\_2, ... , S\_M \\}이 주어진다. NN번째 날에 꿈꾼 직후, 쿠가 S_iS\_i번째 날에 꾼 꿈들만 기억할 수 있는지 판별해 보자.

입력

첫째 줄에 꿈을 꾼 날의 수, 악몽이 영향을 미치는 기간을 의미하는 두 정수 NN, KK가 공백으로 구분되어 주어진다. (1≤K≤N≤200,000)(1\leq K \leq N \leq 200\\, 000)

둘째 줄에 집합 SS의 크기를 의미하는 정수 MM이 주어진다. (1≤M≤N)(1\leq M \leq N)

셋째 줄에 정수 S_1,S_2,⋯ ,S_MS\_1, S\_2, \cdots , S\_M이 공백으로 구분되어 주어진다. (1≤S_1\<S_2<⋯\<S_M≤N)(1\leq S\_1 \<S\_2<\cdots \<S\_M\leq N)

출력

집합 SS에 대해 S_iS\_i번째 날에 꾼 꿈들만 기억할 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제4

  1. 예제 1

    입력
    6 2
2
1 6
    예상 출력
    YES

  2. 예제 2

    입력
    6 2
4
1 4 5 6
    예상 출력
    NO

  3. 예제 3

    입력
    9 3
4
2 3 4 9
    예상 출력
    YES

  4. 예제 4

    입력
    7 6
1
1
    예상 출력
    NO