24534번 - 정원

현욱의 집 앞 정원에는 $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$ 증가하게 된다. 즉, 매일 최대 한 그루의 나무만이 높이가 자라게 된다. 예를 들어, 현욱의 정원에 심긴 나무의 높이가 $1, 3, 4, 5, 5, 7$ 이었다고 하자. 바로 오른쪽 나무와의 높이 차이가 가장 작은 것은 높이 차이가 $1$인 $2$번째, $3$번째 나무이다. 이 중에서 가장 왼쪽 나무는 $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$개 주어진다. 이 때 입력은 항상 $H_i \le H_{i+1}$을 만족한다($1 \le H_i \le 10^9 $)

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

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