import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
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[][] A = new int[N][2];
int[] F = new int[N];
for (int i = 0; i < N; i++) {
A[i][0] = in.nextInt();
F[i] = A[i][0];
A[i][1] = i;
}
Arrays.sort(A, new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
return Integer.compare(ints[0], t1[0]);
}
});
TreeSet<Integer> set = new TreeSet<>();
ArrayList<Integer>[] pair = new ArrayList[N];
for (int i = 0; i < N; i++) {
pair[i] = new ArrayList<>();
}
for (int i = N - 1; i >= 0; i--) {
if (set.lower(A[i][1]) != null) {
pair[set.lower(A[i][1])].add(A[i][1]);
}
if (set.higher(A[i][1]) != null) {
pair[A[i][1]].add(set.higher(A[i][1]));
}
set.add(A[i][1]);
}
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;
SegmentTree(int[] 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, arr);
}
void setOri(int n, int tl, int tr, int[] arr) {
if (tl == tr) {
oriMax[n] = arr[tl];
} else {
int tm = (tl + tr) / 2;
setOri(2 * n, tl, tm, arr);
setOri(2 * n + 1, tm + 1, tr, arr);
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] = 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 |
89 ms |
10988 KB |
Output is correct |
| 2 |
Incorrect |
100 ms |
10620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
10988 KB |
Output is correct |
| 2 |
Incorrect |
100 ms |
10620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2408 ms |
95492 KB |
Output is correct |
| 2 |
Correct |
1124 ms |
95908 KB |
Output is correct |
| 3 |
Correct |
1078 ms |
95052 KB |
Output is correct |
| 4 |
Correct |
2398 ms |
94080 KB |
Output is correct |
| 5 |
Correct |
2270 ms |
96816 KB |
Output is correct |
| 6 |
Correct |
2117 ms |
94488 KB |
Output is correct |
| 7 |
Correct |
2168 ms |
98616 KB |
Output is correct |
| 8 |
Correct |
2179 ms |
98716 KB |
Output is correct |
| 9 |
Correct |
1933 ms |
95980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
10988 KB |
Output is correct |
| 2 |
Incorrect |
100 ms |
10620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
