Fish Feeding Problem

JOI has N fishes numbered from 1 to N, each with an initial intelligence of 0. He has two types of fish food: A and B (in unlimited supply). When a fish eats a piece of food, its intelligence increases as follows:

• If fish k eats a food of type A, its intelligence increases exactly by D.
• If fish k eats a food of type B, then every fish with index ≥ k has its intelligence increased exactly by 1.

The ideal intelligence for fish i is given by C_i. Starting from all fishes having intelligence 0, JOI wants to know if it is possible to perform a sequence of food-addition operations (in any order, and possibly zero operations) so that for a given query defined by indices L and R (1 ≤ L ≤ R ≤ N), every fish with index L, L+1, …, R achieves exactly its ideal intelligence value while the others can be arbitrary. If it is possible, he also wants to know the minimum number of type A food operations required.

The process is additive. Suppose we perform an operation where fish k eats a type A food. Then only fish k gets an increase of D. In contrast, if fish k eats a type B food then every fish with an index ≥ k gets an increase of 1. Note that the order of operations does not matter because the effect is linear.

Observations and Approach:
For fish i (L ≤ i ≤ R), let the number of times a type A food is eaten by fish i be x_i and let the total number of type B operations contributing to fish i be S_i (note that if an operation is performed on fish j with j ≤ i then fish i is affected). Then the overall intelligence of fish i becomes:

\( C_i = x_i \times D + S_i \ \ \text{for } i \in [L,R]. \)

Since type B operations are "free" (we only care about minimizing the number of type A operations), we want to maximize the contribution of type B operations subject to the constraints.

Define S_i by writing it as C_i - k_iD (with \( k_i \ge 0 \)); then x_i = k_i and we must have:

\( S_i = C_i - k_iD, \quad \text{with } 0 \le C_i - k_iD \le C_i. \)

Furthermore, because type B operations affect all fishes with larger indices, the contributions \( S_i \) must form a non-decreasing sequence (i.e. \( S_L \le S_{L+1} \le \cdots \le S_R \)).

The task for a given query is to choose non-negative integers \( k_L, k_{L+1}, \dots, k_R \) minimizing the total \( \sum_{i=L}^{R} k_i \) (which is the number of type A operations) subject to:

\( C_i - k_iD \le C_{i+1} - k_{i+1}D, \quad \text{with } 0 \le k_i \le \lfloor C_i/D \rfloor. \)

A greedy backward algorithm can be used: starting from index R with \( S_R = C_R \) (i.e. \( k_R = 0 \)), for each fish i from R-1 down to L, choose the maximum possible value for \( S_i \) (of the form \( C_i - k_iD \)) that does not exceed the already fixed \( S_{i+1} \). This is computed as:

\( k_i = \left\lceil \frac{C_i - \min(C_i, S_{i+1})}{D} \right\rceil, \quad S_i = C_i - k_iD. \)

If any \( S_i \) becomes negative during the process, then it is impossible to achieve the ideal intelligence for fishes in [L, R].

For each query, if possible, output the minimum number of type A operations required (i.e. \( \sum_{i=L}^{R} k_i \)); otherwise, output -1.

inputFormat

The input is given as follows:

N D
C1 C2 ... CN
Q
L1 R1
L2 R2
... 
LQ RQ

Here, the first line contains two integers N and D (the number of fishes and the increase from a type A food), the second line contains N integers representing the ideal intelligence values C_i for i = 1, …, N. The third line contains an integer Q, the number of queries. Each of the next Q lines contains two integers L and R representing a query.

outputFormat

For each query, output one line containing a single integer: the minimum number of type A operations required to make the intelligence of fishes from index L to R exactly equal their ideal values, or -1 if it is impossible.

sample

5 2
3 5 10 10 10
3
1 3
2 5
1 5

0
0
0

</p>