#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int max_N=100001;
int bin_search(int val,int v[],int st,int dr)
{
    int ans=-1;
    while(st<=dr)
    {
        int med=(st+dr)/2;
        if(v[med]<=val)
        {
            st=med+1;
            ans=med;
        }
        else
            dr=med-1;
    }
    return ans;
}
int bin_search2(int val,int v[],int st,int dr)
{
    int ans=-1;
    while(st<=dr)
    {
        int med=(st+dr)/2;
        if(v[med]>=val)
           {
                ans=med;
                dr=med-1;
           }
        else
            st=med+1;
        
            
    }
    return ans;
}
int main()
{
    int n;
    fin>>n;
    int v[max_N];
    for(int i=1;i<=n;i++)
        fin>>v[i];
    int m;
    int interog,val;
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>interog>>val;
        if(interog==0)
        {
            
            if(v[bin_search(val,v,1,n)]==val)
                fout<<bin_search(val,v,1,n)<<'\n';
            else
                fout<<-1<<'\n';
        }
        else if(interog==1)
        {
            fout<<bin_search(val,v,1,n)<<'\n';
        }
        else
            fout<<bin_search2(val,v,1,n)<<'\n';
        
    }
    
    return 0;
}