#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int lim=1e5+10;
int i,n,Q,t,x,v[lim],l,r,mid,sol;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>Q;
    while(Q--)
    {
        fin>>t>>x;
        if(t==0)
        {
            int sol=1e9;
            l=1;r=n;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(v[mid]==x)
                {
                    sol=mid;
                    l=mid+1;
                }
                else if(v[mid]<x)l=mid+1;
                else r=mid-1;
            }
            if(sol==1e9)fout<<"-1"<<'\n';
            else fout<<sol<<'\n';
        }
        else if(t==1)
        {
            int sol=1;
            l=1;r=n;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(v[mid]<=x)
                    {
                        sol=mid;
                        l=mid+1;
                    }
                else r=mid-1;
            }
            fout<<sol<<'\n';
        }
        else if(t==2)
        {
            int sol=n;
            l=1;r=n;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(v[mid]>=x)
                {
                    sol=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            fout<<sol<<'\n';
        }
    }
    return 0;
}