//logn时间查找任意一段数的新信息

#include<stdio.h>

#include<stdlib.h>

typedef struct node{

int l,r;

int good;

struct node *Ln,*Rn;

}*Linklist,Lnode;

int nice;

int max(int a,int b){ if(a>b)return a; else return b;}

void creat(Linklist list)

{

Linklist p,q;

int h=(list->l+list->r)/2;

if(list->r-list->l==0)

{ list->Ln=NULL;list->Rn =NULL;return; }

p=(Linklist)malloc(sizeof(Lnode));

p->l=list->l ; p->r =h; list->Ln =p; creat(list->Ln );

q=(Linklist)malloc(sizeof(Lnode));

q->l=h+1; q->r=list->r; list->Rn =q; creat(list->Rn );

}

void insert(int rand ,int message,Linklist list)

{

if(list->l==rand&&list->r==rand)

    {list->good=message; return;}

else if(rand<=(list->l+list->r)/2) insert(rand,message,list->Ln );

else                         insert(rand,message,list->Rn );

}

int tongji(Linklist list)

{

if(list->l==list->r )return list->good ;

else list->good =max(tongji(list->Ln),tongji(list->Rn));

return list->good ;

}

int find(int a,int b,Linklist list)

{

int h=(list->l +list->r)/2;

if(list->l==a&&list->r ==b) {nice=list->good;return list->good;}

if(b<=h&&a>=list->l ) find(a , b, list->Ln );

else if(a>h&&b<=list->r ) find(a,b,list->Rn );

else if(a>=list->l&&a<=h&&b<=list->r&&b>h)

     return nice=max(find(a,h,list->Ln ),find(h+1,b,list->Rn ));

return nice;

}

main()

{

int i,a,n,x,y;

Linklist head;

head=(Linklist)malloc(sizeof(node));

head->l=1;

scanf("%d",&n);

head->r=n; creat(head);

for(i=0;i<n;i++)

{

   scanf("%d",&a);

   insert(i+1,a,head);

}

tongji(head);

while(scanf("%d%d",&x,&y))

{

   a=find(x,y,head);

   printf("%d\n",a);

}

return 0;

}