#include <queue>
#include <iostream>
#include <cstdlib>
using namespace std;


struct IntNode{
  int value;
  struct IntNode *left;
  struct IntNode *right;
};

static struct IntNode *create_node(const int v){
  struct IntNode *n=(struct IntNode *)malloc(sizeof(IntNode));
  n->left = n->right = NULL;
  n->value = v;
  return(n);

}

static struct IntNode *insert_node(struct IntNode *n, int v){
  
  if(n==NULL){
    n = create_node(v);
  }
  else if(v<n->value){
    n->left=insert_node(n->left,v);
  }
  else{
    n->right=insert_node(n->right,v);
  }
}
    
      


int main(){
  queue<int> nodes;
  IntNode *First=new IntNode;
  IntNode *Temp=new IntNode;
  IntNode *Temp2=new IntNode;
  int numOfNodes,numOfPairs;
  int j;
  int node,node1,node2;


  cin >> numOfNodes;
  
  while(1){
     First = NULL;
     j=0;
    for(int i = 0;i<numOfNodes;i++){
      
      cin >> node;

      First = insert_node(First,node);
      if(j==0){
      Temp = First;
      Temp2 = First;
      j=1;
      }
    }

    cin >> numOfPairs;
    
    for(int i=0;i<numOfPairs;i++){
      cin >> node1 >> node2;
      Temp=Temp2;

      if(node1>node2){
	node=node1;
	node1=node2;
	node2=node;
      }
      //cout << node1 << " " << node2 << " " << Temp->value << endl;
      if(node1<=Temp->value && node2>Temp->value){
	
	
      }
      else{

	while(1){

	  
	  if(node1>Temp->value){
	    if(node2<=Temp->value){
	      break;   
	    }
	    Temp=Temp->right;

	  }
	  else{
	    if(node2>=Temp->value){
	      break;   
	    } 
		 Temp=Temp->left;

	  }
	}
      }
    
      cout << Temp->value << endl;
    }

    cin >> numOfNodes;
    if(numOfNodes==-1){
      break;
    }
    cout << endl;
  }

   

  return 0;


}