#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int st=1, dr, n,m, a[100001], mid,ans,x=3,y;

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>a[i];
    }

    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;

        if(x==0)
        {
            ans=-1;
            st=1;
            dr=n+1;
            while(st<dr)
            {
                mid=(st+dr)/2;
                if(a[mid]==y)
                {
                    ans=mid;
                    st=mid;
                }

                if(a[mid]>y)
                {
                    dr=mid;
                }
                else
                {
                    st=mid+1;
                }
            }
            fout<<ans<<'\n';
        }

        if(x==1)
        {
            ans=-1;
            st=1;
            dr=n+1;
            while(st<dr)
            {

                mid=(st+dr)/2;

                if(a[mid]>y)
                {
                    dr=mid;
                }
                if(a[mid]<=y)
                {
                    st=mid+1;
                    ans=mid;
                }
            }
            fout<<ans<<'\n';
        }

        if(x==2)
        {
            ans=-1;
            st=1;
            dr=n+1;
            while(st<dr)
            {

                mid=(st+dr)/2;
                if(a[mid]<y)
                {
                    st=mid;
                }
               else
                {
                    ans=mid;
                    dr=mid-1;
                }
            }
            fout<<ans<<'\n';
        }

    }


    return 0;
}