2024-sp_Fish_3 — JOI JOI_spring
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: greedy, data structures, priority queue, segment tree, offline queries

# Fish 3

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)  
Spring Training/Qualifying Trial  
March 20-24, 2024 (Komaba, Tokyo)  
Contest 1 – Fish 3

![](_page_0_Picture_0.jpeg)

JOI-kun is breeding *N* fish in a large tank, and each fish is numbered from 1 to *N*.

JOI-kun has two types of fish food, A and B, both in sufficient quantities. When one piece of food is added to the aquarium, exactly one fish eats it (any fish could potentially eat it), and depending on the type of food and which fish ate it, the intelligence of the fish changes as follows:

- When fish *k* (1 ≤ *k* ≤ *N*) eats one piece of type A food, the intelligence of fish *k* increases exactly by *D*.
- When fish *k* (1 ≤ *k* ≤ *N*) eats one piece of type B food, the intelligence of all fish numbered *k* and above increases exactly by 1 each.

Currently, the intelligence of all fish is 0. JOI-kun wants to make the intelligence of fish *i* (1 ≤ *i* ≤ *N*) equal to its ideal intelligence *C<sub>i</sub>*, but it may not always be possible.

Therefore, he considered *Q* questions. The *j*-th question (1 ≤ *j* ≤ *Q*) is as follows:

- Starting from the state where all fish have an intelligence of 0, by repeating the action of putting food into the aquarium zero or more times, is it possible to reach the state where all fish *L<sub>j</sub>*, *L<sub>j</sub>* + 1, . . . , *R<sub>j</sub>* have their exact ideal intelligence values? Furthermore, if it is possible, what is the minimum number of pieces of type A food that needs to be put into the tank?

Write a program that, given information about JOI-kun's fish and information about the questions, answers his questions.

## Input

Read the following data from the standard input.

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

## Output

Write *Q* lines to the standard output. In the *j*-th line (1 ≤ *j* ≤ *Q*), if it is possible to reach the state where all fish *L<sub>j</sub>*, *L<sub>j</sub>* + 1, . . . , *R<sub>j</sub>* have their exact ideal intelligence values, output the minimum number of pieces of type A food that needs to be put into the tank. Otherwise, output -1.

## Constraints

- 1 ≤ *N* ≤ 300 000.
- 1 ≤ *Q* ≤ 300 000.
- 1 ≤ *D* ≤ 10<sup>12</sup>.
- 0 ≤ *C<sub>i</sub>* ≤ 10<sup>12</sup> (1 ≤ *i* ≤ *N*).
- 1 ≤ *L<sub>j</sub>* ≤ *R<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *Q*).
- Given values are all integers.

## Subtasks

1. (9 points) *N* ≤ 3 000, *Q* ≤ 3 000.
2. (7 points) *C<sub>i</sub>* ≤ 1 (1 ≤ *i* ≤ *N*).
3. (28 points) *D* = 1.
4. (20 points) *C<sub>i</sub>* ≥ *C<sub>i+1</sub>* (1 ≤ *i* ≤ *N* − 1).
5. (36 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 4 2            | 1               |
| 3 1 2 1        |                 |
| 1              |                 |
| 1 3            |                 |

For example, in the following case, all fish 1, 2, 3 eventually have their exact ideal intelligence values, and the number of pieces of type A food put into the tank is 1.

- At first, the intelligence of fish 1, 2, 3, 4 is 0, 0, 0, 0 respectively.
- Next, JOI-kun puts one piece of type B food into the tank, which fish 3 eats. As a result, the intelligence of fish 1, 2, 3, 4 becomes 0, 0, 1, 1 respectively.
- Next, JOI-kun puts one piece of type A food into the tank, which fish 1 eats. As a result, the intelligence of fish 1, 2, 3, 4 becomes 2, 0, 1, 1 respectively.
- Finally, JOI-kun puts one piece of type B food into the tank, which fish 1 eats. As a result, the intelligence of fish 1, 2, 3, 4 becomes 3, 1, 2, 2 respectively.

Since it is impossible to reach the state where all fish 1, 2, 3 have the exact ideal intelligence values without putting any piece of type A food, output 1.

| Sample Input 2 | Sample Output 2 |
| :------------- | :-------------- |
| 4 2            | 0               |
| 0 1 0 1        | -1              |
| 3              | 0               |
| 1 2            |                 |
| 2 3            |                 |
| 1 1            |                 |

This sample input satisfies the constraints of Subtasks 1, 2, 5.

| Sample Input 3 | Sample Output 3 |
| :------------- | :-------------- |
| 5 1            | 5               |
| 3 1 4 1 5      | 3               |
| 3              | 3               |
| 1 5            |                 |
| 2 4            |                 |
| 3 5            |                 |

This sample input satisfies the constraints of Subtasks 1, 3, 5.

| Sample Input 4  | Sample Output 4 |
| :-------------- | :-------------- |
| 6 3             | 9               |
| 16 14 13 8 6 5  | 8               |
| 4               | 0               |
| 1 4             | -1              |
| 2 5             |                 |
| 3 3             |                 |
| 1 6             |                 |

This sample input satisfies the constraints of Subtasks 1, 4, 5.

Starter code: