#include <iostream>
#include <fstream>
using namespace std;

int x[100001];

int cautare_binara_0 (int x[],int nrDeCautat,int n){
int st=1,dr=n,mijloc=0;int gasit=0,i;
while(st<=dr && gasit==0){
    mijloc=(st+dr)/2;
    if(x[mijloc]==nrDeCautat){
        gasit=mijloc;
    }
    else if (x[mijloc]<nrDeCautat)
                st=mijloc+1;
                else
                dr=mijloc-1;
}
if(gasit!=0){
    for(i=gasit;i<=n;i++){
        if(x[i]==x[gasit])
                gasit=i;
                else break;
                }

    return gasit;

}
else
 return -1;
}

int cautare_binara_1 (int x[],int nrDeCautat,int n){
int st=1,dr=n,mijloc=0;int gasit=0,i;
while(st<=dr && gasit==0){
    mijloc=(st+dr)/2;
    if(x[mijloc]==nrDeCautat){
        gasit=mijloc;
    }
    else if (x[mijloc]<nrDeCautat)
                st=mijloc+1;
                else
                dr=mijloc-1;
}
if(gasit==0)
    return dr;
else{
 for(i=gasit;i<=n;i++){
        if(x[i]==x[gasit])
                gasit=i;
                else break;
                }
    return gasit;
}

}

int cautare_binara_2 (int x[],int nrDeCautat,int n){
int st=1,dr=n,mijloc=0;int gasit=0,i;
while(st<=dr && gasit==0){
    mijloc=(st+dr)/2;
    if(x[mijloc]==nrDeCautat){
        gasit=mijloc;
    }
    else if (x[mijloc]<nrDeCautat)
                st=mijloc+1;
                else
                dr=mijloc-1;
}
if(gasit==0)
    return st;
else{
 for(i=gasit;i>=1;i--){
        if(x[i]==x[gasit])
                gasit=i;
                else break;
                }
    return gasit;
}

}
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int rezultat,t,q,i,type,mijloc,st,dr,gasit=0,n,nrDeCautat,raspuns;

    fin>>n;
    for(i=1;i<=n;i++)
        fin>>x[i];
    fin>>t;
    for(q=1;q<=t;q++){
        fin>>type;
        fin>>nrDeCautat;
        switch (type){
        case 0:
        fout<<cautare_binara_0(x,nrDeCautat,n)<<"\n";
        break;
        case 1:
        fout<<cautare_binara_1(x,nrDeCautat,n)<<"\n";
        break;
        case 2:
        fout<<cautare_binara_2(x,nrDeCautat,n)<<"\n";
        break;
        }

    }
return 0;
}



/*
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int rezultat,t,q,i,type,mijloc,st,dr,gasit=0,n,nrDeCautat,raspuns;

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


    fin>>t;
    for(q=1;q<=t;q++){
        fin>>type;
        if(type==0){
            fin>>nrDeCautat;
            rezultat=cautare_binara(x,nrDeCautat,n);
                for(i=rezultat+1;i<=n;i++){
                    if(x[i]==x[rezultat])
                        rezultat=i;
                        else break;
                }
                fout<<rezultat<<"\n";

        }
        if(type==1){
            fin>>nrDeCautat;
            cautare_binara_2(x,nrDeCautat,n,dr,st,gasit);
             rezultat=dr;
             for(i=1;i>=1;i--){
                    if(x[i]==x[rezultat])
                        rezultat=i;
                        else break;
                }
            cout<<rezultat<<"\n";
        }
        if(type==2){
            fin>>nrDeCautat;
            cautare_binara_2(x,nrDeCautat,n,dr,st,gasit);
            cout<<x[st];
        }




    }









    return 0;
}
*/