#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100001];

int main()
{
    int n;
    fin>>n;
    for (int i=1; i<=n; i++ )
    {
        fin>>v[i];
    }
    int m;
    fin>>m;
    while ( m-- )
    {
        int tip,x;
        fin >>tip>>x;
        
        
        
        
        if ( tip==0 )
        {
            int st=1,dr=n,ans=-1;
            while ( st <= dr )
            {
                int mijl=(st+dr)/2;
                if ( v[mijl]==x )
                {
                    ans=mijl;
                    st=mijl+1;
                }
                else if ( v[mijl]<x )
                {
                    st=mijl+1;
                }
                else 
                {
                    dr=mijl-1; 
                }
            }
            fout<<ans<<'\n';
        }
        
        
        
        
        else if ( tip==1 )
        {
            int st=1,dr=n,ans=-1;
            while ( st <= dr)
            {
                
                int mijl=(st+dr)/2;
                if ( v[mijl]<=x ) 
                {
                    ans=mijl; 
                    st=mijl+1; 
                }
                
                else 
                {
                    dr=mijl-1; 
                }
            }
            fout<<ans<<'\n';
        }
        
        
        
        
        else
        {
            int st=1, dr=n, ans=-1;
            while ( st <= dr )
            {
                
                int mijl=(st+dr)/2;
                if ( v[mijl]>=x ) 
                {
                    ans=mijl; 
                    dr=mijl-1; 
                }
                
                else
                {
                    st=mijl+1;
                }
            }
            fout<<ans<<'\n';
        }
    }
    return 0;
}