////#include <iostream>
////
////using namespace std;
////long long s,p,j,S;
////int main()
////{   long long n;
////    cin>>n;
////    p=n*(n+1)%10234573;
////    cout<<p<<" ";
////    j=(2*n+1)%10234573;
////    cout<<j<<endl;
////    S=p*j/6;
////    cout<<S<<endl;
////    s=(n*(n + 1)*(2*n + 1))/6;
////    cout<<s;
////    return 0;
////}
//// Ordonare sort divide et impera
//#include <iostream>
//#include <fstream>
//using namespace std;
//long long s,p,j,S;
//void sortare(int n,int a[1005]){
//    int i,mij,j,pivot;
//    i=1;
//    j=n;
//    mij=n/2;
//    pivot=a[mij];
//    while(i<j){
//        if(a[i]>a[j])
//        {swap(a[i],a[j]);
//        i++;
//        }
//        else
//        if(a[i]<a[j])
//        {swap(a[i],a[j]);
//        j--;
//        }
//    }
//
//}
//int main()
//{   long long n,i;
//    int a[1000];
//    cin>>n;
//   for(i=1;i<=n;i++)
//    cin>>a[i];
//   sortare(n,a);
//   for(i=1;i<=n;i++)
//    cout<<a[i]<<" ";
//    return 0;
//}
////maximpar
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("maximpar.in");
//ofstream fo("maximpar.out");
//int maxim,apare,n,a[10000],ok,i;
//int main(){
//    fi>>n;
//    for(i=1;i<=n;i++)
//    {fi>>a[i];
//        if(a[i]%2==0 and a[i]>maxim)
//        {   apare=0;
//        ok=1;
//            apare++;
//            maxim=a[i];
//        }
//        else
//        if(a[i]==maxim)
//            apare++;
//
//    }
//    if(ok==1)
//    fo<<maxim<<" "<<apare;
//    else
//        fo<<"-1";
//}
////prima cifra minima
//#include <iostream>
//#include <fstream>
//using namespace std;
//long long n,a[10001],MIN,i,nrmin,aux;
//int main(){
//    cin>>n;
//    for(i=1;i<=n;i++)
//    cin>>a[i];
//    MIN=10;
//    for(i=1;i<=n;i++)
//    {
//    aux=a[i];
//    while(aux>9)
//        aux=aux/10;
//    if(aux<MIN )
//    {MIN=aux;
//        nrmin=a[i];
//    }
//    else
//    if(aux==MIN and nrmin<a[i])
//        nrmin=a[i];
//    }
//    cout<<nrmin;
//}
////Max impar
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("maximpar.in");
//ofstream fo("maximpar.out");
//int maxim,apare,n,a[10000],ok,i,x,y,k;
//int main(){
//    cin>>n;
//    for(i=1;i<=n;i++)
//    cin>>a[i];
//    x=a[1];
//    y=min(a[2],a[3]);
//    for(i=1;i<=n;i++){
//    if(a[i]>x)
//            {x=a[i]; k=0; k++;}
//            else
//            if(a[i]==x)
//                k++;
//    }
//    if(k>1)
//    {y=x;
//    cout<<y<<" "<<x;
//    }
//    else
//        {for(i=1;i<=n;i++)
//          if(a[i]>y and a[i]!=x)
//            y=a[i];
//   cout<<x<<" "<<y;}
//}
//#include <iostream>
//#include <algorithm>
//using namespace std;
//int i,n,a[10000];
//int main(){
//    cin>>n;
//    for(i=1;i<=n;i++)
//        cin>>a[i];
//    sort(a,a+n+1);
//        cout<<a[3]<<" "<<a[2]<<" "<<a[1];
//}

////NRDIV
//#include <iostream>
//#include <fstream>
//#include <cmath>
//using namespace std;
//int i,n,C,x,nrdiv;
////void divizori(int x)
////{
////    int nrdiv;
////    nrdiv=2;
////    for(i=2; i*i<=x; i++)
////        if(i*i==x)
////            nrdiv+=1;
////        else
////        if(x%i==0)
////            nrdiv+=2;
////
////    if(x!=1)
////        cout<<nrdiv<<" ";
////    else
////        cout<<"1"<<" ";
////}
//int main()
//{
//    cin>>n;
//    for(i=0; i<n; i++)
//    {
//        x=pow(2,i)*i+1;
//    nrdiv=2;
//    for(i=2; i*i<=x; i++)
//        if(i*i==x)
//            nrdiv+=1;
//        else
//        if(x%i==0)
//            nrdiv+=2;
//
//        cout<<nrdiv<<" ";
//    }
//}

////MChenar
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int a[101][101],n,i,j,m,C,fr[1000001],maxi;
//int main()
//{
//    cin>>n>>m;
//    for(i=1; i<=n; i++)
//        for(j=1; j<=m; j++)
//            {cin>>a[i][j];
//            fr[a[i][j]]++;
//            if(a[i][j]>maxi)
//                maxi=a[i][j];
//            }
//     for(i=maxi;i>=0;i--)
//         if(fr[i]>1)
//         {
//             cout<<i<<" ";
//             return 0;
//         }
//         cout<<"IMPOSIBIL";
//         return 0;
//}

////ColEgale
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int a[101][101],n,i,j,m,C,fr[1000001],maxi,ok,oky;
//int main()
//{
//    cin>>n>>m;
//    for(i=1; i<=n; i++)
//        for(j=1; j<=m; j++)
//            cin>>a[i][j];
//     for(i=1; i<=m; i++)
//        {  ok=1;
//            for(j=1; j<n; j++)
//            {
//                if(a[j][i]!=a[j+1][i])
//                    ok=0;
//            }
//            if(ok==1)
//                {cout<<a[j][i]<<" ";oky=1;}
//        }
//        if(oky==0)
//            cout<<"nu exista";
//}

//#include <fstream>
//#include <iostream>
//#include <cmath>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long x,ok,k,i;
//int main()
//{
//    ok=1;
//    while(ok){
//            cin>>x;
//            if(x==0)
//                return 0;
//            if(x%2==0)
//                k++;
//                 }
//                 cout<<k;
//}

//#include <iostream>
//#include <fstream>
//#include <cmath>
//#include <iomanip>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//double x,y,z;
//double nr;
//int main(){
//    cin>>x>>y>>z;
//    nr=(x+y+z)/3;
//    cout<<setprecision(2)<<nr;
//
//}

////TIMP 1 PBINFO
//#include <iostream>
//#include <iomanip>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int h1,m1,x,h2,m2,hadg,minadg;
//int main () {
//    cin>>h1>>m1>>x;
//    hadg=x/60; minadg=x-hadg*60;
//    m2=m1+minadg;
//    if(m2>59)
//    {m2=m2-60;
//    hadg++;
//    }
//        h2=h1+hadg;
//        while(h2>=24)
//        {
//         h2=h2-24;
//        }
//    cout<<h2<<" "<<m2;
//}

//#include <iostream>
//#include <iomanip>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long x,y,maxi,K,P;
//char s;
//int main () {
//    cin>>x>>y>>s;
//    if(s=='+')
//        cout<<x+y;
//    if(s=='-')
//    {if(x>y)
//        cout<<x-y;
//        else
//            cout<<y-x;}
//    if(s=='*')
//        cout<<x*y;
//    if(s=='/')
//    {if(x>y)
//        cout<<x/y;
//        else
//            cout<<y/x;}
//
//}


//#include <iostream>
//#include <iomanip>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long x,y,maxi,K,P;
//char s;
//int main () {
//    cin>>n>>z;
//    for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//            cin>>a[i][j];
//    if(z==1)
//    for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//}

//#include <iostream>
//#include <iomanip>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long x,y,maxi,K,P,a[1000][1000];
//char s;
//int zona1 (int n)
//{
//    int i,j,s=0;
//    for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//            if(i+j<n+1 and i<j)
//                s+=a[i][j];
//        return s;
//}
//int zona3(int n){
//    int i,j,s=0;
//        for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//            if(i+j>n+1 and i>j)
//                 s+=a[i][j];
//    return s;
//}
//int zona4(int n){
//    int i,j,s=0;
//        for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//            if(i+j<n+1 and i>j)
//                s+=a[i][j];
//    return s;
//}
//int zona2(int n){
//    int i,j,s=0;
//for(i=1;i<=n;i++)
//    for(j=1;j<=n;j++)
//            if(i+j>n+1 and i<j)
//                 s+=a[i][j];
//    return s;
//}
//int main () {
//    int i,j,n,z;
//    cin>>n>>z;
//    for(i=1;i<=n;i++)
//        for(j=1;j<=n;j++)
//            cin>>a[i][j];
//    if(z==1)
//        cout<<zona1(n);
//    if(z==2)
//        cout<<zona2(n);
//    if(z==3)
//        cout<<zona3(n);
//    if(z==4)
//        cout<<zona4(n);
//}


#include <iostream>
#include <fstream>
using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int n,m,x[100001],y[100001];
int cauta0(int c){
    int st,dr,mij,gasit=0;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x[mij]==c and x[mij+1]!=c)
            return mij;
        if(x[mij]<=c)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}
int cauta1(int c){
    int st,dr,mij,gasit=0;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x[mij]==c and x[mij+1]!=c)
            return mij;
        if(x[mij]<=c)
            st=mij+1;
        else
            dr=mij-1;
    }
    return mij-1;
}
int cauta2(int c){
    int st,dr,mij,gasit=0;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x[mij]==c)
            {
                while(x[mij]==c)
                    mij--;
                return mij+1;
            }
        if(x[mij]<=c)
            st=mij+1;
        else
            dr=mij-1;
    }
    if(x[mij-1]<=c and x[mij]>c)
        return mij;
    else
    return mij+1;
}
int main(){
    int i,a,b;
    fi>>n;
    for(i=1;i<=n;i++)
        fi>>x[i];
    fi>>m;
    for(i=1;i<=m;i++)
    {
        fi>>a>>b;
        if(a==0)
            fo<<cauta0(b)<<'\n';
            else
                if(a==1)
                fo<<cauta1(b)<<'\n';
                else
                    fo<<cauta2(b)<<'\n';
    }
}