#include <fstream>
//#include <algorithm>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,v[100001],x,p,u,y,t,m,w;
int main(){
    f>>n;
    for(i=1;i<=n;++i)
        f>>v[i];
    //sort(v+1,v+n+1);
    f>>m;
    for(i=1;i<=m;++i)
    {
        f>>w>>x;
        p=1;
        u=n;
        t=0;
        while(p<=u && t==0)
        {
            y=(p+u)/2;
            if(v[y]==x)
                t=y;
            else
                if(v[y]<x)
                    p=y+1;
                else
                    u=y-1;
        }
        if(w==0)
            if(t==0)
                g<<-1<<'\n';
            else
            {
                while(v[t+1]==x)
                    t++;
                g<<t<<'\n';
            }
        else
           if(w==1){
               if(t==0)
                    t=p;
               if(x>v[n])
                   g<<n<<'\n';
               else {
                    while(v[t]>x)
                        --t;
                    g<<t<<'\n';
               }
            }
            else
                if(w==2){
                    if(t==0)
                        t=u;
                    if(v[t]<x)
                        t++;
                    else
                        while(v[t-1]>=x)
                            t--;
                    g<<t<<'\n';
                }
    }
    g.close();
    return 0;
}