정원

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

요약

정렬된 나무 높이가 주어질 때 매일 오른쪽 나무와의 차이가 가장 작은 가장 왼쪽 나무가 1 자란다. 각 K일 뒤 가장 큰 나무와 가장 작은 나무의 높이 차를 구합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 이분 탐색, 배열
정답자: 아직 제출이 없습니다

문제

현욱의 집 앞 정원에는 나무 $N$ 그루가 있다( $1 \le N \le 3 \cdot 10^5$ ). 나무의 높이는 $1$ 이상 $10^9$ 이하의 정수이고, 높이가 오름차순이 되도록 심어져 있다. 즉, $i$ 번째 나무의 높이를 $H_i$ 라고 하면 항상 $H_i \le H_{i+1}$ 이 성립한다.

정원의 나무 중 아래 두 조건을 모두 만족하는 나무는 하루가 지나면 높이가 $1$ 증가한다.

바로 오른쪽 나무보다 높이가 낮다( $H_i < H_{i+1}$ ).
이런 나무들 중에서 바로 오른쪽 나무와의 높이 차이가 가장 작다.

조건을 만족하는 나무가 여러 그루라면 그중 가장 왼쪽에 있는 나무만 자란다. 즉, 하루에 최대 한 그루의 높이만 자란다. 예를 들어 나무의 높이가 $1, 3, 4, 5, 5, 7$ 이라고 하자. 바로 오른쪽 나무와의 높이 차이가 가장 작은 나무는 2번째와 3번째 나무이고, 차이는 모두 $1$ 이다. 이 중 가장 왼쪽의 2번째 나무의 높이가 $1$ 자란다.

현욱은 오늘부터 $K$ 일 후에 가장 높은 나무와 가장 낮은 나무의 높이 차이가 얼마인지 알고 싶어졌다( $1 \le K \le 10^{12}$ ). 현욱의 질문이 $Q$ 번 주어질 때( $1 \le Q \le 3 \cdot 10^5$ ), 각 질문에 답하는 프로그램을 작성하라.

입력

첫 줄에 나무의 수 $N$ 과 질문의 수 $Q$ 가 주어진다( $1 \le N, Q \le 3 \cdot 10^5$ ).

둘째 줄에 나무의 높이 $H_i$ 가 순서대로 공백으로 구분되어 $N$ 개 주어진다( $1 \le H_i \le 10^9$ ). 입력은 항상 $H_i \le H_{i+1}$ 을 만족한다.

셋째 줄부터 $Q$ 줄에 걸쳐 질문이 주어진다. 모든 $K$ 는 $1$ 이상 $10^{12}$ 이하의 정수이다.

출력

각 질문에 대해, $K$ 일 후 정원에서 가장 높은 나무와 가장 낮은 나무의 높이 차이를 한 줄에 하나씩 출력한다.

예제1

예제 1
입력
```
5 6
1 3 3 4 5
2
3
5
6
8
10
```
예상 출력
```
4
4
4
3
1
0
```