记录编号	55269	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.853 s
提交时间	2013-03-17 17:02:53	内存使用	45.94 MiB

Program cog58;
    Type
        Tr=Record
               A,B,M:Longint;
           End;
    Var
        A:Array[1..4000000]Of Tr;
        N,Q,I,H,L,R:Longint;
    Function Max(A,B:Longint):Longint;
        Begin
            If A>B Then Exit(A);
            Exit(B);
        End;
    Procedure Build(P,L,R:Longint);
        Var
            M:Longint;
        Begin
            A[P].A:=L;
            A[P].B:=R;
            A[P].M:=-Maxlongint;
            If L=R Then Exit;
            M:=(L+R) Shr 1;
            Build(P Shl 1,L,M);
            Build(P Shl 1+1,M+1,R);
        End;
    Procedure Up(P,N,R:longint);
        Var
            M:Longint;
        Begin
            If A[P].M<N Then A[P].M:=N;
            If A[P].A=A[P].B Then Exit;
            M:=(A[P].A+A[P].B) Shr 1;
            If R<=M
                Then Up(P Shl 1,N,R)
                Else Up(P Shl 1+1,N,R)
        End;
    Function Ask(P,L,R:Longint):Longint;
        Var
            M:Longint;
        Begin
            If (A[P].A=L) And (A[P].B=R) Then Exit(A[P].M);
            M:=(A[P].A+A[P].B) Shr 1;
            If R<=M Then Exit(Ask(P Shl 1,L,R))
            Else If L>M Then Exit(Ask(P Shl 1+1,L,R))
            Else Exit(Max(Ask(P Shl 1,L,M),Ask(P Shl 1+1,M+1,R)));
        End;
    Begin
        Assign(Input,'climb.in');
        Assign(Output,'climb.out');
        Reset(Input);
        Rewrite(Output);
        Readln(N);
        Build(1,0,N);
        For I:=0 To N Do
            Begin
                Readln(H);
                Up(1,H,I);
            End;
        Readln(Q);
        For I:=1 To Q Do
            Begin
                Readln(L,R);
                Writeln(Ask(1,L,R));
            End;
        Close(Input);
        Close(Output);
    End.