#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int main()
{
    int x,q,v[100002],i,n,s=1,d,mj,r,m;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
        n++;
        v[n]=INT_MAX;
    f>>m;
    for(i=1;i<=m;i++)
    {
        s=1;
        d=n;
        f>>q>>x;
        if(q<2)
        {
            while(s<=d)
            {
                mj=(s+d)/2;
                if(v[mj]>x)
                {
                    r=mj;
                    d=mj-1;
                }
                else
                {
                    s=mj+1;
                }
            }
            if(q==0)
            {
                if(v[r-1]==x)
                    g<<r-1;
                else
                    g<<-1;
            }
            else
                g<<r-1;
        }
        else
        {
            while(s<=d)
            {
                mj=(s+d)/2;
                if(v[mj]>=x)
                {
                    r=mj;
                    d=mj-1;
                }
                else
                {
                    s=mj+1;
                }
            }
            g<<r;
        }
        g<<'\n';
    }
    return 0;
}