#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, v[100001], i, j, minn, aux, p, k, st, dr, mid, sol, x, m, ok;

int main(){

         fin>>n;

         for(i=1;i<=n;i++)
                  fin>>v[i];

        fin>>m;
         for(i=1;i<=m;i++){
                  fin>>p>>x;
                  if(p==0){
                           st=1; dr=n;
                           ok=0;
                           while(st<=dr){
                                    mid=(st+dr)/2;
                                    if(v[mid]<=x){
                                             st=mid+1;
                                             if(v[mid]==x)
                                                      ok=1;
                                    }
                                    else
                                             dr=mid-1;
                           }
                           if(ok==1)
                                    fout<<dr<<'\n';
                           else
                                    fout<<-1<<'\n';

                  }

                  if(p==1){
                           st=1; dr=n;
                           while(st<=dr){
                                    mid=(st+dr)/2;
                                    if(v[mid]<=x)
                                             st=mid+1;
                                    else
                                             dr=mid-1;
                           }
                           fout<<dr<<'\n';

                  }

                  if(p==2){
                           st=1; dr=n;
                           while(st<=dr){
                                    mid=(st+dr)/2;
                                    if(v[mid]>=x)
                                             dr=mid-1;
                                    else
                                             st=mid+1;
                           }
                           fout<<st<<'\n';

                  }
        }
        fin.close();
        fout.close();
return 0;
}