#include<bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in"); ofstream g("cautbin.out");
int v[100001];
int main ()
{   int n,T;
    f>>n;
    for(int i=1;i<=n;++i) f>>v[i];
    f>>T;
    while(T--)
	{   int tip,val;
	    f>>tip>>val;
		if(tip==0)
        {   int p=1,u=n,m;
            while(p<=u)
            {   m=(p+u)/2;
                if(v[m]<=val) p=m+1; else u=m-1;
            }
            m=(p+u)/2;
            if(val<v[m]) --m;
            if(val!=v[m]) m=-1;
            g<<m<<'\n';
        }
		if(tip==1)
        {   int p=1,u=n,m;
            while(p<u)
            {   m=(p+u)/2;
                if(v[m]<=val) p=m+1; else u=m;
            }
            m=(p+u)/2;
            if(val<v[m]) --m;
            g<<m<<'\n';
        }
		if(tip==2)
        {   int p=1,u=n,m;
            while(p<u)
            {   m=(p+u)/2;
                if(v[m]<val) p=m+1; else u=m;
            }
            m=(p+u)/2;
            if(v[m]<val) ++m;
            g<<m<<'\n';
        }
    }
    g.close(); return 0;
}