#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,a[100010],ics,apel;
long long n,m;
int divide_et_impera0(int left,int right,int x)
{
    int mij;
    if(left<=right)
    {
        mij=left+(right-left)/2;
        cout<<left<<" "<<right<<" "<<mij<<"\n";
        if(a[mij]==x)
        {
            if(a[mij+1]!=x || mij==n-1)
                return mij;
            else
                return divide_et_impera0(mij+1,right,x);
        }
        if(a[mij]>x)
        {
            return divide_et_impera0(left,mij-1,x);
        }
        if(a[mij]<x)
        {
            if(a[mij+1]>x || mij==n-1)
                return -2;
            else
                return divide_et_impera0(mij+1,right,x);
        }
    }
}
int divide_et_impera1(int left,int right,int x)
{
    int mij;
    if(left<=right)
    {

        mij=left+(right-left)/2;
        //cout<<left<<" "<<right<<" "<<a[mij+1]<<"\n";
        if(a[mij]<=x)
        {
            if(a[mij+1]>x || mij==n-1)
            {
                //cout<<"a gasit"<<a[mij]<<"\n";
                return mij;

            }
            else
                return divide_et_impera1(mij+1,right,x);
        }
        if(a[mij]>x)
        {
            return divide_et_impera1(left,mij-1,x);
        }
    }
}
int divide_et_impera2(int left,int right,int x)
{
    int mij;
    if(left<=right)
    {
        mij=left+(right-left)/2;
        if(a[mij]==x)
        {
            if(a[mij-1]!=x || mij==0)
            {
                return mij;
            }

            else
                return divide_et_impera2(left,mij-1,x);
        }
        if(a[mij]>x)
        {
            if(a[mij-1]<x || mij==0)
                return mij;
            else
                return divide_et_impera2(left,mij-1,x);

        }
        if(a[mij]<x)
        {
            return divide_et_impera2(mij+1,right,x);
        }
    }
}


int main()
{
    f>>n;
    for(i=0; i<n; i++)
    {
        f>>a[i];
    }
    f>>m;

    for(i=0; i<m; i++)
    {
        f>>apel>>ics;
        if(apel==0)
            g<<divide_et_impera0(0,n-1,ics)+1<<"\n";
        if(apel==1)
            g<<divide_et_impera1(0,n-1,ics)+1<<"\n";
        if(apel==2)
            g<<divide_et_impera2(0,n-1,ics)+1<<"\n";
    }

    //f>>apel>>ics;
    //g<<divide_et_impera1(0,n-1,ics)+1;

    return 0;
}
/*
Cerinta:
https://www.infoarena.ro/problema/cautbin
Solutie1
Avem o functie divide_et_impera pe care o apelam cu right si left;
Intrand in functie calculam mijlocul array-ului.
Apoi comparam val din mijl cu elem cautat:
Daca valoarea din mijl este mai mica sau egala cu elem cautat,
        daca valoarea din [mij+1] este mai mare decat elem cautat => atunci mij este solutia.
        else apelam functia cu left=mij+1 si right=right.
Else apelam functia left=left si right=mij-1;
*/
///complexitate:O(log2(n))