#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
using namespace std;

struct intreb{
int intr;
int val;
};
intreb a[100001];
int v[100001];
int frecv[100001];
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
        frecv[v[i]]=frecv[v[i]]+1;
    }
    int m;
    fin>>m;
    for(int i=1;i<=m;i++){
        fin>>a[i].intr>>a[i].val;
    }

    for(int i=1;i<=m;i++){
        if(a[i].intr==0){
            int st=1;
            int dr=n;
            int ok=-1;
            int mij;
            while(st<=dr){
               mij=(st+dr)/2;
                if(a[i].val<v[mij]){
                    dr=mij-1;
                }
                if(a[i].val>v[mij]){
                    st=mij+1;

                }
                if(a[i].val==v[mij]){
                    ok=0;
                    break;
                }

            }
            if(ok==-1){
                fout<<-1<<'\n';
            }
            else{
                while( mij<n &&v[mij]==a[i].val){

                mij++;
                }
                fout<<mij-1<<'\n';
            }
        }


        if(a[i].intr==1){
            int st=1;
            int dr=n;
            int ok=-1;
            int mij;
            while(st<=dr){
              mij=(st+dr)/2;
                if(a[i].val<v[mij]){
                    dr=mij-1;
                }
                if(a[i].val>v[mij]){
                    st=mij+1;

                }
                if(a[i].val==v[mij]){
                    ok=0;
                    break;
                }

            }
           while(v[mij]==a[i].val && mij<n){

           mij++;
           }
          fout<<mij-1<<'\n';

    }

    if(a[i].intr==2){
            int st=1;
            int dr=n;
            int ok=-1;
            int  mij;
            while(st<=dr){
               mij=(st+dr)/2;
                if(a[i].val<v[mij]){
                    dr=mij-1;
                }
                if(a[i].val>v[mij]){
                    st=mij+1;

                }
                if(a[i].val==v[mij]){
                    ok=0;
                    break;
                }

            }
            if(frecv[a[i].val]==1){
            fout<<mij-1<<'\n';
        }
        else{
            while(v[mij]==a[i].val && mij>=1){

            mij--;
            }

            fout<<mij+1<<'\n';
        }
    }



}
}