#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,m,i,j,st,dr,mid,ce,v[100005],poz,x;
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    cin>>m;
    for(i=1; i<=m; i++)
    {
        cin>>ce>>x;
        if(ce==0)
        {
            st=1;
            dr=n;
            poz=-1;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(v[mid]==x)
                {
                    poz=mid;
                    st=mid+1;
                }
                else
                    if(v[mid]<x)
                    st=mid+1;
                else
                    dr=mid-1;
            }
            cout<<poz<<'\n';
        }
        else if(ce==1)
        {
            st=1;dr=n;poz=0;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(v[mid]<=x)
                {
                    poz=mid;
                st=mid+1;
                }
                else
                    dr=mid-1;
            }
            cout<<poz<<'\n';
        }
        else if(ce==2)
        {
          st=1;
          dr=n;
          poz=0;
          while(st<=dr)
          {
              mid=(st+dr)/2;
              if(v[mid]>=x)
              {
                poz=mid;
                dr=mid-1;
              }
              else
                st=mid+1;
          }
           cout<<poz<<'\n';

        }
    }
    return 0;
}