//ST表(离线)

 //预处理 O(n*lgn) , 查询 O(1)

 #include <iostream>

 #include <stdio.h>

 using namespace std;

 #define MX 10005

 int n;

 int a[MX];

 int st[MX][]; // st[i][j] 是第 i 个数为左端点长为 2^j 区间的最大值

 int lgn[MX]; //lgn[i] 是 lgn(i) 的值

 void Init()

 {

     lgn[]=-;

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

     {

         if ((i&(i-))==) lgn[i]=lgn[i-]+;

         else lgn[i]=lgn[i-];

         st[i][]=a[i];

     }

     for (int i=;i<=lgn[n];i++) //区间长为 2^i 次方

         for (int j=;j+(<<i)-<=n;j++)

             st[j][i]=max(st[j][i-],st[j+(<<(i-))][i-]);

 }

 int inquery(int a,int b)

 {

     int k = lgn[b-a+];

     return max(st[a][k],st[b-(<<k)+][k]);

 }

 int main()

 {

     scanf("%d",&n);

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

         scanf("%d",&a[i]);

     Init();

     int m;

     scanf("%d",&m);

     while (m--)

     {

         int l,r;

         scanf("%d%d",&l,&r);

         printf("%d\n",inquery(l,r));

     }

     return ;

 }