#include <bits/stdc++.h>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[100005],m;

int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    while(m--)
    {
        int cer,x;
        f>>cer>>x;
        assert(cer==0||cer==1||cer==2);
        if(!cer)
        {
            int st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                int mi=(st+dr)>>1;
                if(v[mi]<=x)
                {
                    if(v[mi]==x)
                        poz=mi;
                    st=mi+1;
                }
                else
                    dr=mi-1;
            }
            g<<poz<<'\n';
        }
        else if(cer==1)
        {
            int st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                int mi=(st+dr)>>1;
                if(v[mi]<=x)
                {
                    poz=mi;
                    st=mi+1;
                }
                else
                    dr=mi-1;
            }
            g<<poz<<'\n';
        }
        else
        {
            int st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                int mi=(st+dr)>>1;
                if(v[mi]>=x)
                {
                    poz=mi;
                    dr=mi-1;
                }
                else
                    st=mi+1;
            }
            g<<poz<<'\n';
        }
    }
    return 0;
}