#include <iostream>
#include <fstream>
#define dim 25001
using namespace std;
int a[dim];
int main()
{
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    int n,m,x,i,tip;
    int st,dr,mij,poz;
    bool ok;
    cin>>n;for(int i=1;i<=n;++i)cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>tip>>x;
        if(tip==0)
        {
        /**************************************/
        st=1;
        dr=n;
        ok=0;poz=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(x==a[mij]) {ok=1;if(poz<mij)poz=mij;st=mij+1;}
            else if(x<a[mij]) dr=mij-1;
            else st=mij+1;
        }
        if(ok)
            cout<<poz<<'\n';
        else
            cout<<-1<<'\n';
        /**************************************/
        }

        else if(tip==1)
        {
        /**************************************/
        st=1;
        dr=n;
        poz=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(x>=a[mij])
                {if(poz<mij)poz=mij;st=mij+1;}
            else //if(x<a[mij])
                dr=mij-1;
           }
            cout<<poz<<'\n';
        /**************************************/
        }

        else if(tip==2)
        {
        /**************************************/
        st=1;
        dr=n;
        poz=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(x<=a[mij]) //e ok
                {if(poz>mij)poz=mij;dr=mij-1;}
            else
                st=mij+1;
        }
        cout<<poz<<'\n';
        /**************************************/
        }
    }
    cout<<'\n';
    return 0;
}

        /**************************************/
//        st=1;
//        dr=n;
//        ok=0;
//        while(st<=dr)
//        {
//            mij=(st+dr)/2;
//            if(x==a[mij]) {ok=1;break;}
//            else if(x<a[mij]) dr=mij-1;
//            else st=mij+1;
//        }
        /**************************************/