#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,a[100010],i,j,x,s,q,ok,poz,k;
int main()
{
    fin>>n;
    for(i=0;i<n;i++)
        fin>>a[i];
    fin>>m;
    for(i=0;i<m;i++)
    {
        fin>>q>>x;
        switch(q)
        {
            case 0:
            {
                for(s=1;s<n;s<<=1);
                for(j=0;s;s>>=1)
                    if(j+s<n && a[j+s]<=x)
                        j+=s;
                if(j==0 && a[0]!=x)
                    fout<<"-1\n";
                else
                    fout<<j+1<<'\n';
            }break;
            case 1:
            {
                for(s=1;s<n;s<<=1);
                for(j=0;s && !ok;s>>=1)
                {
                    if(j+s<n && a[j+s]<=x)
                        j+=s;
                    if(a[j]==x)
                        ok=1;
                }
                poz=j;
                for(k=poz;k<n;k++)
                    if(a[k]<=x)
                        j=k+1;
                fout<<j<<'\n';
            }break;
            case 2:
            {
                ok=0;
                for(s=1;s<n;s<<=1);
                for(j=0;s;s>>=1)
                    if(j+s<n && a[j+s]<=x)
                        j+=s;
                if(j==0 && a[0]!=x)
                    poz=n-1;
                else
                    poz=j;
                for(k=poz;k>=0;k--)
                    if(a[k]>=x)
                        j=k+1;
                fout<<j<<'\n';
            }break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}