题目描述

题目译自 JOISC 2024 Day1 T1 「魚 3 / Fish 3」

JOI 君在一个大型水箱养了 $N$ 条鱼，并且对所有鱼从 $1$ 到 $N$ 编号。

JOI 君有足量的两种饲料 A 和 B，每次投放一片饲料后，有且仅有一条鱼会吃它。根据饲料类型，会对鱼的智力产生不同效果：

鱼 $k\enspace (1\le k\le N)$ 吃了一片饲料 A 之后，鱼 $k$ 的智力增加 $D$。

鱼 $k\enspace (1\le k\le N)$ 吃了一片饲料 B 之后，鱼 $k$ 和所有编号大于 $k$ 的鱼的智力各增加 $1$。

目前所有鱼的智力均为 $0$。JOI 君希望鱼 $i\enspace (1\le i\le N)$ 的智力等于预期值 $C_i$，但这不一定能做到。

他考虑了 $Q$ 个问题。其中第 $j\enspace (1\le j\le Q)$ 个问题形如：

从初始状态（即所有鱼的智力均为 $0$）开始，依次投放若干片饲料（可以不投放任何饲料），并可以指定吃每一片饲料的鱼，是否可能使鱼 $L_j, L_j+1,\dots, R_j$ 的智力均和预期值 $C$ 一致？如果可以，请给出至少要投放多少片饲料 A。

给定鱼、饲料和询问信息，写一个程序求解询问。

输入格式

从标准输入读入以下内容：

$ND$

$C1C2⋯ CN$

$Q$

$L1R1$

$L2R2$

$⋮$ $LQRQ​$ ​ ​

。

输出格式

输出 $Q$ 行，每行一个整数，对于其中第 $j\enspace (1\le j\le Q)$ 行，若鱼 $L_j,L_j+1,\dots ,R_j$ 可以同时恰好达到预期的智力值，输出最少需要投放的饲料 A 的片数；否则输出 $-1$

样例1：

4 2
3 1 2 1
1
1 3

1

经过以下操作，鱼 $1,,2,,3$ 最终均可达到预期的智力值，且仅需要 $1$ 片饲料 A。

鱼 $1,,2,,3,,4$ 的智力依次分别为 $0,,0,,0,,0$。

JOI 君首先投放一片饲料 B，鱼 $3$ 吃了之后，四条鱼的智力依次为 $0,,0,,1,,1$。

投放一片饲料 A，鱼 $1$ 吃了之后，四条鱼的智力依次为 $2,,0,,1,,1$。

最后投放一片饲料 B，鱼 $1$ 吃了之后，四条鱼的智力分别为 $3,,1,,2,,2$。

由于不投放任何饲料 A 无法使鱼 $1,,2,,3$ 分别恰好达到智力值 $1,,2,,3$，因此输出 $1$。

这组样例满足子任务 $1,,5$ 的限制。

样例2：

4 2
0 1 0 1
3
1 2
2 3
1 1

0
-1
0

这组样例满足子任务 $1,,2,,5$ 的限制。

样例3：

5 1
3 1 4 1 5
3
1 5
2 4
3 5

5
3
3

这组样例满足子任务 $1,,3,,5$ 的限制。

样例4：

6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6

9
8
0
-1

这组样例满足子任务 $1,,4,,5$ 的限制。

数据规模与约定

对于所有数据，满足：

$1\le N\le 300,000$

$1\le Q\le 300,000$

$1\le D\le 10^{12}$

$0\le C_i\le 10^{12}\enspace (1\le i\le N)$

$1\le L_j\le R_j\le N\enspace (1\le j\le Q)$

所有输入的数均为整数。

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	$N \le 3,000,\enspace Q \le 3,000$	$9$
$2$	$C_i\le 1\enspace (1\le i\le N)$	$7$
$3$	$D=1$	$28$
$4$	$C_i\ge C_{i+1}\enspace (1\le i\le N-1)$	$30$
$5$	无附加限制	$36$