#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int v[100001];
int cautbin(int b,int n){
    long long st=1,dr=n,mijl,poz=-1;
    while(st<=dr){
        mijl=(st+dr)/2;
        if(b==v[mijl]){
            poz=mijl;
            break;
        }
        else if (b<v[mijl])
        dr=mijl-1;
        else
        st=mijl+1;
    }
   return poz;
}
int main()
{long long n,c,a,b,i,x;
in>>n;
for(i=1; i<=n; i++)
    in>>v[i];
in>>c;
for(i=1; i<=c; i++){
    in>>a>>b;
    if(a==0){
     if(cautbin(b,n)==-1)
     out<<-1<<endl;
     else{
         long long  y=cautbin(b,n),cn=n;
         while(cn>=y){
             if(v[cn]==b){
                 out<<cn<<endl;
                 break;
             }
             cn--;
         }
     }
    }
    else if (a==1){
        int maxi=0;
        for(int j=1; j<=b; j++){
            long long  y=cautbin(b,n),cn=n;
            if(cautbin(j,n)!=-1){
             while(cn>=y){
             if(v[cn]==j){
                 break;
             }
             cn--;
         }
         if(cn>maxi)
         maxi=cn;
            }
        }
        out<<maxi<<endl;
    }
    else {
         int maxi=100001;
        for(int j=b; j<=n; j++){
            long long  y=cautbin(b,n),cn=1;
            if(cautbin(j,n)!=-1){
             while(cn<=n){
             if(v[cn]==j){
                 break;
             }
             cn++;
         }
         if(cn<maxi)
         maxi=cn;
            }
        }
        out<<maxi<<endl;
    }
 
}
    return 0;
}