시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)276660.000%

문제

BOJ 국가는 좌우로 길쭉한 영토를 가지고 있다. 영토는 수직선 상의 길이 $L$짜리 선분으로 나타낼 수 있으며, 영토의 왼쪽 끝은 좌표 $0$, 오른쪽 끝은 좌표 $L$에 각각 놓여 있다.

BOJ 국가의 영토에는 깃발이 총 $N$개 꽂혀 있는데, 이 중 왼쪽에서 $i$번째 깃발은 정수 좌표 $X_i$에 꽂혀 있다. 깃발이 너무 한 군데에 몰려 있으면 보기에 좋지 않기 때문에, 임의의 두 깃발은 적어도 $K$ 이상의 거리를 가지도록 하는 규정이 있다. 현재 꽂혀 있는 $N$개의 깃발은 이 규정을 지킨다.

신년을 맞이하여 BOJ 국가에서는 깃발 $M$개를 추가로 꽂기로 하였고, BOJ 국가의 공무원인 당신은 이것을 새해 첫 업무로 배정받았다. 깃발을 꽂기 위해서 당신은 특정 좌표에서 깃발 $M$개를 들고 출발한다. 당신은 영토 내에서 좌우로 자유롭게 이동할 수 있으며, 현재 서 있는 위치가 정수 좌표라면 언제든지 깃발을 꽂을 수 있다. 단, 규정을 지키기 위해서 이미 꽂힌 깃발을 포함하여 임의의 두 깃발이 적어도 $K$ 이상의 거리를 가지도록 깃발 $M$개를 꽂아야 한다. 규정을 지키면서 깃발 $M$개를 꽂을 수 없는 경우는 주어지지 않는다.

당신은 가능한 출발지로 총 $Q$개의 후보를 골라 이 중 하나에서 출발하기로 했으며, $i$번째 후보는 정수 좌표 $P_i$에 위치한다. 이동 거리가 길수록 퇴근이 늦어지기 때문에, 당신은 각 후보에서 출발할 때 $M$개의 깃발을 모두 꽂는 데에 필요한 최소 이동 거리를 알고 싶다. 빠른 퇴근을 위해 이 값들을 구하여 보자.

입력

첫 번째 줄에 $N$, $M$, $K$, $L$, $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $X_i$가 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $P_i$가 주어진다.

출력

$Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $i$번째 후보에서 출발할 때 $M$개의 깃발을 모두 꽂는 데 필요한 최소 이동 거리를 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $1\le N,Q\le 200\, 000$
  • $1\le M,K,L\le 10^9$
  • $0\le X_i\le L$ $(1\le i\le N)$
  • $X_i+K\le X_{i+1}$ $(1\le i\le N-1)$
  • $0\le P_i\le L$ $(1\le i\le Q)$
  • 규정을 지키면서 깃발 $M$개를 추가로 꽂을 수 있다.

예제 입력 1

3 3 2 20 5
5 10 19
12
4
2
20
9

예제 출력 1

4
9
7
7
7

예제에서 $M=3$, $K=2$이다. 즉, 깃발 3개를 추가로 꽂아야 하며, 임의의 두 깃발은 최소 2만큼 떨어져 있어야 한다.

첫 번째 후보인 좌표 12에서 출발할 경우, 16까지 이동하면서 12, 14, 16에 깃발 3개를 꽂으면 이동 거리가 4가 된다. 더 짧게 움직이는 방법은 없으므로 답은 4이다.

두 번째 후보인 좌표 4에서 출발할 경우, 우선 7까지 이동하여 7에 깃발 하나를 꽂고, 다시 1까지 이동하면서 3, 1에 깃발 2개를 더 꽂으면 이동 거리가 9가 된다. 더 짧게 움직이는 방법은 없으므로 답은 9이다.

출처

Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2024! F번