#include <bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int n,v[100008],i,nr,op,q,aux;
int cout_bin2(int val)
{
    int st=0,dr=n+1,mij;
    while(dr-st>1)
    {
        mij=(dr+st)/2;
        if(v[mij]<=val)
            st=mij;
            else
            dr=mij;
    }
    return st;
}
int cout_bin3(int val)
{
    int st=0,dr=n+1,mij;
    while(dr-st>1)
    {
        mij=(dr+st)/2;
        if(v[mij]<val)
            st=mij;
            else
            dr=mij;
    }
    return dr;
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>op>>nr;
        if(op==0)
        {
            aux=cout_bin2(nr);
            if(v[aux]==nr)
                cout<<aux;
                else
                cout<<-1;
        }
        else
        if(op==1)
        {
            cout<<cout_bin2(nr);
        }
        else
        {
            cout<<cout_bin3(nr);
        }
        cout<<'\n';
    }
    return 0;
}