#P13529. [2025年队测]预言

    ID: 12713 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-有限候选集缩减单调栈最近更大/更小元素离线查询懒标记线段树

[2025年队测]预言

题意描述

在地球上,时间可以理解为是一个一维的数轴(一个序列)。一个时间节点上的蝴蝶效应可以理解为是一个正整数。由于一开始已经进行了一些操作,所以第 ii 个时间节点上的蝴蝶效应为一个正整数 viv_i。

具体来说,小W\text{W} 将会做出 qq 次「预言」。一次「预言」需要两个参数 l,rl,r,表示需要从区间 [l,r][l,r] 中选择三个不同的时间节点 l≤a<b<c≤rl\le a\lt b\lt c\le r,但是由于技术不成熟,三个时间节点还要求 b−a≤c−bb-a\le c-b。且一次「预言」的评估值为选中的三个时间节点上的蝴蝶效应的累加和即 va+vb+vcv_a+v_b+v_c。由于形势迫在眉睫,小W\text{W} 希望评估值尽可能大。

可是 小W\text{W} 不会解决这个问题,为了帮助她成为救世主,你需要告诉她每次「预言」可能的评估值的最大值。

输入格式

第一行一个正整数 n (1≤n≤5×105)n\ (1\le n\le 5\times 10^5) 表示时间轴的长度。

第二行 nn 个正整数 ai (1≤ai≤108)a_i\ (1\le a_i \le 10^8) 表示初始时第 ii 个时间节点上的蝴蝶效应。

第三行一个整数 q (1≤q≤5×105)q\ (1\le q\le 5\times 10^5) 表示「预言」的次数。

接下来第 44 至 q+3q+3 行,每行两个整数 l,r (1≤l≤r≤n, r−l+1≥3)l,r\ (1\le l\le r\le n,\ r-l+1\ge3),表示 小W\text{W} 向你询问一次「预言」操作的最大评估值。

输出格式

qq 行表示每次「预言」的可能评估值的最大值。

样例

样例输入 #1
5
5 2 1 5 3
3
1 4
2 5
1 5
样例输出 #1
12
9
12
样例输入 #2
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
样例输出 #2
277
227
72
262
178
181
174
257
208
262
262
113

数据范围

对于 15%15\% 的数据,1≤n,q≤1021\le n,q \le 10^2。

对于 30% 的数据,1≤n≤50001\le n\le5000。

对于另外 15%15\% 的数据,1≤n≤2×105,q=l=1,r=n1\le n\le 2\times 10^5,q=l=1,r=n。

对于 100%100\% 的数据,$1\le n,q \le 5 \times 10 ^ 5,1\le l\le r\le n,\ r-l+1\ge3$。

本站保证每个询问至少包含三个时间节点。