#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
unsigned long long v[100010];
unsigned long long x,n,m;
unsigned long long min1,max1;
void citire()
{
    fin>>n;
    for(int a1=1;a1<=n;a1++)
    {
        fin>>v[a1];
    }
    fin>>m;
}
void fct0()
{
    unsigned long long k;
    if(min1!=max1)
    {
        k=(min1+max1)/2;
        if(v[k]==x)
        {
            while(v[k]==x)
            {
                k++;
            }
            fout<<k-1<<'\n';
        }
        else if(v[k]>x)
        {
            max1=k;
            fct0();
        }
        else
        {
            min1=k+1;
            fct0();
        }
    }
    else if(v[min1]==x)
    {
            while(v[min1]==x)
            {
                min1++;
            }
            fout<<min1-1<<'\n';
    }
    else fout<<"-1"<<'\n';
}
void fct1()
{
    unsigned long long k;
    if(min1!=max1)
    {
        k=(min1+max1)/2;
        if(v[k]==x)
        {
            while(v[k]==x)
            {
                k++;
            }
            fout<<k-1<<'\n';
        }
        else if(v[k]>x)
        {
            max1=k;
            fct1();
        }
        else
        {
            min1=k+1;
            fct1();
        }
    }
    else if(v[min1]==x)
    {
            while(v[min1]==x)
            {
                min1++;
            }
            fout<<min1-1<<'\n';
    }
    else
    {
        if(v[min1]<x)
        {
            fout<<min1<<'\n';
        }
        else fout<<min1-1<<'\n';
    }
}
void fct2()
{
    unsigned long long k;
    if(min1!=max1)
    {
        k=(min1+max1)/2;
        if(v[k]==x)
        {
            while(v[k]==x)
            {
                k--;
            }
            fout<<k+1<<'\n';
        }
        else if(v[k]<x)
        {
            min1=k+1;
            fct2();
        }
        else
        {
            max1=k;
            fct2();
        }
    }
    else if(v[min1]==x)
    {
        while(v[min1]==x)
        {
            min1--;
        }
        fout<<min1+1<<'\n';
    }
    else
    {
        if(v[min1]<x) fout<<min1+1<<'\n';
        else fout<<min1<<'\n';
    }
}
int main()
{
    citire();
    int t;
    for(int a=1;a<=m;a++)
    {
        fin>>t>>x;
        min1=1;
        max1=n;
        if(t==0) fct0();
        if(t==1) fct1();
        if(t==2) fct2();
    }
}