#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 main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];

    }
    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(v[mij-1]!=v[mij]&& v[mij+1]!=v[mij]){
            fout<<mij-1<<'\n';
        }
        else{
            while(v[mij]==a[i].val && mij>=1){

            mij--;
            }

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



}
}