#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 100005
#define MAXM 130005
using namespace std;

struct node {
   int x_min, x_max;
   int x_max_max, x_max_min, x_min_max, x_min_min;
   int y_max, z_min;
};

int v[MAXN];
node arbint[2 * MAXN];

void Build(int nod, int left, int right) {
   if(left == right) {
      arbint[nod].x_min = arbint[nod].x_max = v[left];
      arbint[nod].x_max_max  = arbint[nod].x_min_min = 2 * v[left];
      arbint[nod].x_max_min = arbint[nod].x_min_max = 0;
      arbint[nod].y_max = v[left];
      arbint[nod].z_min = v[left];
   }
   else {
      int mid = (left + right) / 2;
      Build(2 * nod, left, mid);
      Build(2 * nod + 1, mid + 1, right);

      arbint[nod].x_min = min(arbint[2 * nod].x_min, arbint[2 * nod + 1].x_min);
      arbint[nod].x_max = max(arbint[2 * nod].x_max, arbint[2 * nod + 1].x_max);

      arbint[nod].y_max = 0;
      for(int i = left; i <= right)

      arbint[nod].x_max_max  = arbint[nod].x_min_min = 2 * v[left];
      arbint[nod].x_max_min = arbint[nod].x_min_max = 0;
      arbint[nod].y_max = v[left];
      arbint[nod].z_min = v[left];
   }
}

int minW(int st, int dr) {

}

int Query(int nod, int left, int right, int st, int dr) {
   int max_y = 0, min_z = - (1 << 24);
   if(left >= st && right <= dr) {
      max_y = max( max(arbint[nod].y_max, arbint[nod].x_max_max - minW(arbint[nod].x_max_max)), max(arbint[nod].x_min_max + maxw);
   }
   else {
      int mid = (left + right) / 2;
      if(st <= mid) {
         int x = Query(2 * nod, left, mid, st, dr);
         if(x > ans)
            ans = x;
      }
      if(mid < dr) {
         int x = Query(2 * nod + 1, mid + 1, right, st, dr);
         if(x > ans)
            ans = x;
      }
   }
   return ans;
}
int main()
{
    ifstream cin("eq.in");
    ofstream cout("eq.out");
    cin >> N;
    for(int i = 1; i <= N; ++i) {
      cin >> v[i];
    }
    Build(1, 1, N);
    cin >> M;
    for(int i = 1; i <= M; ++i) {
      cin >> x >> y;
      cout << Query(1, 1, N, x, y) << '\n';
    }
    return 0;
}