import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Vector;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class jumps {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TripleJumps solver = new TripleJumps();
solver.solve(1, in, out);
out.close();
}
static class TripleJumps {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int N = in.nextInt();
int[] F = new int[N];
for (int i = 0; i < N; i++) {
F[i] = in.nextInt();
}
Stack<Integer> stack = new Stack<>();
ArrayList<Integer>[] pair = new ArrayList[N];
for (int i = 0; i < N; i++) {
pair[i] = new ArrayList<>();
}
stack.add(0);
for (int i = 1; i < N; i++) {
while (stack.size() > 0 && F[stack.peek()] >= F[i]) {
pair[stack.pop()].add(i);
}
if (!stack.isEmpty()) {
pair[stack.peek()].add(i);
}
stack.add(i);
}
int Q = in.nextInt();
ArrayList<int[]>[] query = new ArrayList[N];
for (int i = 0; i < Q; i++) {
int l = in.nextInt() - 1;
int r = in.nextInt() - 1;
if (query[l] == null) {
query[l] = new ArrayList<>();
}
query[l].add(new int[]{r, i});
}
int[] ans = new int[Q];
SegmentTree seg = new SegmentTree(F);
for (int l = N - 2; l >= 0; l--) {
if (pair[l] != null) {
for (int a : pair[l]) {
seg.upd(1, 0, N - 1, 2 * a - l, N - 1, F[a] + F[l]);
}
}
if (query[l] != null) {
for (int[] r : query[l]) {
ans[r[1]] = seg.query(1, 0, N - 1, l + 2, r[0]);
}
}
}
for (int i : ans) {
out.println(i);
}
}
class SegmentTree {
int[] max;
int[] lzy;
int[] oriMax;
int[] arr;
SegmentTree(int[] arr) {
this.arr = arr;
max = new int[4 * arr.length];
oriMax = new int[4 * arr.length];
lzy = new int[4 * arr.length];
setOri(1, 0, arr.length - 1);
}
void setOri(int n, int tl, int tr) {
if (tl == tr) {
oriMax[n] = arr[tl];
} else {
int tm = (tl + tr) / 2;
setOri(2 * n, tl, tm);
setOri(2 * n + 1, tm + 1, tr);
oriMax[n] = Math.max(oriMax[2 * n], oriMax[2 * n + 1]);
}
}
void push(int n) {
lzy[2 * n] = Math.max(lzy[2 * n], lzy[n]);
lzy[2 * n + 1] = Math.max(lzy[2 * n + 1], lzy[n]);
max[2 * n] = Math.max(max[2 * n], oriMax[2 * n] + lzy[2 * n]);
max[2 * n + 1] = Math.max(max[2 * n + 1], oriMax[2 * n + 1] + lzy[2 * n + 1]);
lzy[n] = 0;
}
void upd(int n, int tl, int tr, int l, int r, int val) {
if (l <= tl && tr <= r) {
max[n] = Math.max(max[n], oriMax[n] + val);
lzy[n] = Math.max(lzy[n], val);
} else if (l > tr || r < tl) {
return;
} else {
push(n);
int tm = (tl + tr) / 2;
upd(2 * n, tl, tm, l, r, val);
upd(2 * n + 1, tm + 1, tr, l, r, val);
max[n] = Math.max(max[2 * n], max[2 * n + 1]);
}
}
int query(int n, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r) {
return max[n];
} else if (l > tr || r < tl) {
return 0;
} else {
push(n);
int tm = (tl + tr) / 2;
return Math.max(query(2 * n, tl, tm, l, r),
query(2 * n + 1, tm + 1, tr, l, r));
}
}
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Compilation message
Note: jumps.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
10224 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
10716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
10224 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
10716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1238 ms |
93844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
10224 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
10716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
