记录编号	371102	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.525 s
提交时间	2017-02-15 15:00:50	内存使用	4.91 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cctype>
#include <ctime>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  inline int readint(){
    char c; int r; bool s = false;
    while(c = readc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30;break;
      }else if(c == '-')s = true;
    }
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
  }
}; using IO::readint; using IO::readc;
struct node{
  node *ls, *rs;
  int size;
  int fix;
  int val, maxv;
  int lazy;
  node(int v):val(v), size(1), fix(rand()), lazy(0){
    ls = rs = NULL;
    maxv = val;
  }
  #define SIZE(x) ((x)?(x)->size:0)
  #define MAXV(x) ((x)?(x)->maxv:-0x7fffffff)
  void pushup(){
    if(!this)return;
    size = SIZE(ls)+SIZE(rs)+1;
    maxv = max(val, max(MAXV(ls), MAXV(rs)));
  }
  void pushdown(){
    if(!this)return;
    if(lazy){
      ls->getup(lazy);
      rs->getup(lazy);
      lazy = 0;
    }
  }
  void getup(int v){
    if(!this)return;
    val += v;
    maxv += v;
    lazy += v;
  }
}*root;
typedef pair<node *, node *>droot;
typedef node *pnode;
struct range{
  node *left, *middle, *right;
};
droot split(node *x, int k){
  if(!x)return droot(NULL, NULL);
  x->pushdown();
  droot r(NULL, NULL);
  if(SIZE(x->ls) >= k){
    r = split(x->ls, k);
    x->ls = r.second;
    x->pushup();
    r.second = x;
  }else{
    r = split(x->rs, k-SIZE(x->ls)-1);
    x->rs = r.first;
    x->pushup();
    r.first = x;
  }
  return r;
}
node *merge(node *x, node *y){
  if(!x){y->pushup(); return y;}
  if(!y){x->pushup(); return x;}
  if(x->fix < y->fix){
    x->pushdown();
    x->rs = merge(x->rs, y);
    x->pushup();
    return x;
  }else{
    y->pushdown();
    y->ls = merge(x, y->ls);
    y->pushup();
    return y;
  }
}
range get_range(int l, int r){
  droot p1 = split(root, l-1);
  droot p2 = split(p1.second, r-l+1);
  return (range){p1.first, p2.first, p2.second};
}
inline void merge_range(range r){
  root = merge(r.left, merge(r.middle, r.right));
}
node *build(int *a, int n){
  pnode *stk = new pnode[n];
  node *last;
  int tp = 0;
  for(int i = 0; i < n; i++){
    node *p = new node(a[i]);
    last = NULL;
    while(tp && stk[tp-1]->fix > p->fix){
      stk[tp-1]->pushup();
      last = stk[tp-1];
      stk[--tp] = NULL;
    }
    if(tp)stk[tp-1]->rs = p;
    p->ls = last;
    stk[tp++] = p;
  }
  while(tp)stk[--tp]->pushup();
  node *r = stk[0];
  delete []stk;
  return r;
}
void dfs(node *u){
  if(!u)return;
  u->pushdown();
  dfs(u->ls);
  printf("%d\n", u->val);
  dfs(u->rs);
}
int a[2000001];
int main(){
 // freopen("test_data.out", "r", stdin);
  freopen("climb.in", "r", stdin);
  freopen("climb.out", "w", stdout);
 // freopen("equake2.in", "r", stdin);
 // freopen("equake2.out", "w", stdout);
  srand(time(NULL));
  int n = readint(); //int q = readint();
  for(int i = 0; i <= n; i++)a[i] = readint();
  root = build(a, n+1);
  int q = readint();
  while(q--){
    int l = readint(); int r = readint();
    range rg = get_range(l+1, r+1);
    printf("%d\n", rg.middle->maxv);
    merge_range(rg);
  }
  /*
  while(q--){
    char c;
    while(!isalpha(c = readc()));
    if(c == 'R'){
      int l = readint(); int r = readint();
      int v = readint();
      range rg = get_range(l, r);
      rg.middle->getup(v);
      merge_range(rg);
    }else if(c == 'I'){
      int p = readint();
      int k = readint();
      droot sp = split(root, p);
      for(int i = 0; i < k; i++)a[i] = readint();
      node *rt = build(a, k);
      root = merge(sp.first, merge(rt, sp.second));
    }else if(c == 'Q'){
      int l = readint(); int r = readint();
      range rg = get_range(l, r);
      printf("%d\n", rg.middle->maxv);
      merge_range(rg);
    }else if(c == 'M'){
      int l = readint(); int r = readint();
      range rg = get_range(l, r);
      root = merge(rg.left, rg.right);
    }
  }
  */
  return 0;
}