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.util.Comparator;
import java.util.Collections;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
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<int[]> iter = new ArrayList<>();
stack.add(0);
for (int i = 1; i < N; i++) {
while (stack.size() > 0 && F[stack.peek()] <= F[i]) {
iter.add(new int[]{stack.pop(), i});
}
if (!stack.isEmpty()) {
iter.add(new int[]{stack.peek(), i});
}
stack.add(i);
}
int Q = in.nextInt();
for (int i = 0; i < Q; i++) {
int l = in.nextInt() - 1;
int r = in.nextInt() - 1;
iter.add(new int[]{l, r, i});
}
Collections.sort(iter, new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
if (ints[0] == t1[0]) {
return Integer.compare(ints.length, t1.length);
} else {
return Integer.compare(t1[0], ints[0]);
}
}
});
int[] ans = new int[Q];
SegmentTree seg = new SegmentTree(F);
for (int l = 0; l < iter.size(); l++) {
int[] t = iter.get(l);
if (iter.get(l).length == 2) {
seg.upd(1, 0, N - 1, 2 * t[1] - t[0], N - 1, F[t[1]] + F[t[0]]);
} else {
ans[t[2]] = seg.query(1, 0, N - 1, t[0] + 2, t[1]);
}
}
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
jumps.java:20: error: class Main is public, should be declared in a file named Main.java
public class Main {
^
1 error
