P11392 [JOI Open 2019] 三段跳び

**译自 [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

无

无

#### 样例解释： 在第一次跳跃中，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 Lj < Lj + 2 \le Rj \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 分）无额外约束。