만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

디버깅

면접 대비

시간 제한0.6초메모리 제한512 MB

요약
N개 줄 중 M개 오류 줄 번호가 주어질 때, 인규가 최소 Y개 오류를 직접 고친 뒤 편집기가 X개의 연속된 정상 줄을 감지해 자동으로 고칠 수 있는 오류 수의 최댓값을 구한다.
난이도

보통10점 중 5점

유형
투 포인터, 슬라이딩 윈도우, 그리디, 배열
정답자
아직 제출이 없습니다

문제

인규는 코드를 자동으로 생성해 주는 프로그램을 이용해 코드를 작성하곤 한다.

하지만 AI는 완벽하지 않기 때문에 자동으로 생성된 코드에 오류가 있을 수도 있다.

그래서 인규는 코드를 자동으로 생성한 뒤, 코드를 한 줄씩 읽으면서 오류를 찾는다.

인규가 쓰는 코드 에디터는 매우 똑똑해서 작성된 코드에서 오류가 없는 연속된 XX줄이 존재하면, 특정 커맨드로 나머지 오류를 자동으로 해결할 수 있다. 즉, 인규는 자동으로 생성된 코드를 전부 수정하지 않고도 프로그램을 완성할 수 있다.

다만 인규는 코드 에디터에 의존하는 것을 싫어하기 때문에, 오류를 YY개 이상 찾아 해결한 뒤에만 에디터의 오류 해결 기능을 이용하려 한다.

음이 아닌 두 정수 XX, YY와 자동으로 생성된 코드에서 오류가 있는 줄 번호가 주어질 때, 에디터가 해결할 오류 개수의 최댓값을 구하는 프로그램을 작성하시오.

단, 한 줄에는 최대 한 개의 오류만 존재한다.

입력

첫 줄에는 자동으로 작성된 코드 줄의 수 NN과 오류가 있는 줄의 개수 MM이 주어진다. (1≤N≤2×107(1 \le N \le 2 \times 10^7, 1≤M≤min⁡(N, 5×105))1 \le M \le \min(N,\ 5\times 10^5))

두 번째 줄에는 코드에서 오류가 있는 줄의 번호 MM개가 공백으로 구분되어 주어진다.

다음 줄에는 정수 XX, YY가 공백으로 구분되어 주어진다. (0≤X≤N(0 \le X \le N, 0≤Y≤M)0 \le Y \le M)

출력

에디터가 해결할 오류 개수의 최댓값을 출력한다.

예제2

  1. 예제 1

    입력
    5 4
    1 3 4 5
    2 2
    
    예상 출력
    2
    
  2. 예제 2

    입력
    10 4
    1 4 7 10
    1 3
    
    예상 출력
    1