#3153. 「JOI Open 2019」三级跳

内存限制:537 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI Open 2019 T1 「三段跳び / Triple Jump

有一条很长的路,被划分为 N 段并从 1 N 编号。每一段都一个坚固程度,第 i 段路的坚固程度为 A_i

JOI 君是一位有天赋的体育明星。他将在这条路上进行三级跳。一次三级跳包含三次连续的跳跃动作。设 a,b,c 为 JOI 君进行三级跳时三个起跳点的所在段,那么需要满足以下条件:

  • a<b<c 。即:起跳点所在段需要严格递增;
  • b-a\le c-b 。即:第一次的跳跃距离应该不大于第二次的跳跃距离。

JOI 君将进行 Q 次三级跳。第 j 次三级跳的所有起跳点所在段编号都在 L_j R_j 范围内。换句话说,必须保证 L_j\le a<b<c\le R_j

JOI 君想在更坚固的段上起跳。对于每次三级跳,JOI 君想知道起跳点的最大坚固程度之和。

写一个程序,在给定路的段数和每次三级跳的信息的情况下,计算对于每次三级跳,起跳点的最大坚固程度之和。

输入格式

第一行一个整数 N ,表示路的段数;

第二行 N 个整数 A_i ,第 i 个数表示第 i 段路的坚固程度;

第三行一个整数 Q ,表示 JOI 君进行了 Q 次三级跳;

接下来 Q 行,每行两个整数 L_j,R_j ,表示每次三段跳进行的区间。

输出格式

输出 Q 行,第 j\ (1\le j\le Q) 行表示对第 j 个询问做出的回答。

样例

样例输入 1

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

样例输出 1

12
9
12

样例说明 1

对于第一次三级跳,JOI 君在 1,2,4 段起跳,最大坚固程度之和为 5+2+5=12

对于第二次三级跳,JOI 君在 3,4,5 段起跳,最大坚固程度之和为 1+5+3=9 ,如果他在 2,4,5 段起跳,得到的坚固程度之和为 10 ,但这不满足 b-a\le c-b ,因此舍去;

对于第三次三级跳,JOI 君在 1,2,4 段起跳,最大坚固程度之和为 5+2+5=12 ,如果他在 1,4,5 段起跳,得到的坚固程度之和为 13 ,但这不满足 b-a\le c-b ,因此舍去。

样例输入 2

5
5 4 4 5 4
1
1 5

样例输出 2

14

样例说明 2

这组数据满足子任务 3 的限制条件。

样例输入 3

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13

样例输出 3

277
227
72
262
178
181
174
257
208
262
262
113

数据范围与提示

对于所有数据, 3\le N\le 5\times 10^5,1\le Q\le 5\times 10^5,1\le A_i\le 10^9,1\le L_j\lt L_j+2\le R_j\le N

详细子任务附加限制及分值如下表:

子任务编号 附加限制 分值
1 N,Q\le 100 5
2 N\le 5\times 10^3 14
3 N\le 2\times 10^5,Q=1,L_1=1,R_1=N 27
4 无附加限制 54