P11392 [JOI Open 2019] 三级跳 / Triple Jump

**译自 [JOI Open 2019](https://contests.ioi-jp.org/open-2019/index.html) T1 「三段跳び」** 有一条路，包含 $N$ 段，编号 $1\sim N$。第 $i$ 段有一个强度 $A_i$。 JOI 君，有天赋的体育明星，准备来三段跳。一个三段跳包含三次连续的跳跃。令 $a,b,c$ 分别表示 JOI-kun 三次起跳的段编号，他们需要满足以下条件。 - $a

第 $1$ 行 $1$ 个整数 $N$。 第 $2$ 行 $N$ 个整数，代表 $A_1,A_2,\cdots,A_n$。 第 $3$ 行 $1$ 个整数 $Q$。 第 $4\sim 4+Q-1$ 行，每行两个整数 $L_i,R_i$。

输出 $Q$ 行。每行输出一个整数，表示答案。

#### 样例解释： 在第一次跳跃中，JOI 君可以选择 $1,2,4$ 段，从而达到最大加和 $12$。 在第二次跳跃中，JOI 君可以选择 $3,4,5$ 段，从而达到最大加和 $9$。如果选择 $2,4,5$，虽然和是 $10$，但是 $b-a\le c-b$ 没有满足。 在第三次跳跃中，JOI 君可以选择 $1,2,4$ 段，从而达到最大加和 $12$。如果选择 $1,4,5$，虽然和是 $13$，但是 $b-a\le c-b$ 没有满足。 #### 数据范围： - $3 \le N \le 5 \times 10^5$。 - $1 \le A_i \le 10^8 (1 \le i \le N)$。 - $1 \le Q \le 5 \times 10^5$。 - $1 \le L_j < L_j + 2 \le R_j \le N (1 \le j \le Q)$。 #### 子任务： 1. （5 分）$N\le 100$，$Q\le 100$。 2. （14 分）$N\le 5000$。 3. （27 分）$N\le 2\times 10^5$，$Q=1$，$L_1=1$，$R_1=N$。 4. （54 分）无额外约束。