/* 
    Title : RMQ(Range Minimum Query)問(wèn)題的Binary Tree解法， 
            查詢一指定數(shù)列任意一段區(qū)間內(nèi)最(大)元素的位置 
    Time Complex : O(n) 預(yù)處理， O(logn) 每次查詢 
    Space Complex : O(3*n) Total space 
    Author : song 
    Date : 9.3.2005 
*/ 
#include <cstdio> 
#include <iostream>
using namespace std;
const int MAX = 1<<16;  //MAX is a power of 2 and just bigger than n 
int key[MAX];           //數(shù)列 
int n;                  //數(shù)列長(zhǎng)度 
int pp[MAX*2];          //binary tree數(shù)組,pp[i]保存i子樹覆蓋的區(qū)間里最值的序號(hào) 

inline bool RMQcmp(int i, int j)    //比較函數(shù) 
{ 
    //like a heap, here we us > to get a Minimum Result, 
    //and < to get a Maximum one 
    return key[i] > key[j];      
}    

void RMQCreate()           //預(yù)處理，建樹 
{ 
     int f = MAX, t = MAX + n - 1, i; 
     for(i = 0; i < n; ++i) 
        pp[i+MAX] = i; 
     for( ;f < t; f /= 2, t /= 2) 
     { 
        for(i = f; i < t ; i+= 2) 
        { 
            if( !RMQcmp(pp[i], pp[i+1]) ) 
                pp[i/2] = pp[i]; 
            else pp[i/2] = pp[i+1]; 
        } 
        if(!(t&1)) pp[t/2] = pp[t]; 
     } 
} 

int RMQFind(int ss, int ee)     //返回原數(shù)列key[ss - ee]之間最大(小)元素的序號(hào) 
{ 
    int k, f, t; 
    ss += MAX, ee += MAX; 
    k = !RMQcmp(pp[ss] ,pp[ee]) ? pp[ss] : pp[ee]; 
    for( f = ss, t = ee; f < t; f/=2, t/=2) 
    { 
        if( !(f&1) && f + 1 < t && !RMQcmp(pp[f+1], k)) 
            k = pp[f+1]; 
        if( (t&1)  && t - 1 > f && !RMQcmp(pp[t-1], k)) 
            k = pp[t-1]; 
    } 
    return k; 
} 

int main() 
{ 
    /* 
        main()里做的事： 
        1.先初始化好key數(shù)列,及比較函數(shù)RMQcmp()。key[]的名字可改，只要cmp對(duì)應(yīng)上就行。 
        2.調(diào)用RMQCreate()預(yù)處理 
        3.查詢key[0,n-1]之間最大(小)元素的序號(hào)，只需調(diào)用RMQFind(0, n-1) 
    */
	int num,a,b,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&key[i]);
	RMQCreate();
	scanf("%d",&num);
	for(;num;num--)
	{
		cin>>a>>b;
		cout<<key[RMQFind(a-1,b-1)]<<endl;
	}
    return 0; 
}