#include <fstream>
//#include <iostream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int cautare_bin1(int v[],int left,int right,int target)
{
    int mid = (left + right) / 2, poz = 0;
    
    while(left <= right)
    {
        mid = (left + right) / 2;
        
        if(v[mid] <= target){
            left = mid +1;
            poz = mid;
        }
        else{
            right = mid - 1;
        }
    }
    
    
    if(v[poz] == target)
        return poz;
    
    return -1;
}

int cautare_bin2(int v[],int left,int right,int target)
{
    int mid = (left + right) / 2, poz = 0;
    
    while(left <= right)
    {
        mid = (left + right) / 2;
        
        if(v[mid] <= target){
            left = mid +1;
            poz = mid;
        }
        else
            right = mid - 1;
        
    }
    
    return poz;
    
}

int cautare_bin3(int v[],int left,int right,int target)
{
    int mid = (left + right) / 2, poz = 0;
    
    while(left <= right)
    {
        mid = (left + right) / 2;
        
        if(v[mid] >= target){
            poz = mid;
            right = mid - 1;
            }
        else
            left = mid + 1;
        
    }
    
    return poz;
}

int main()
{
    int v[100020],n,nr_caz,caz,target;
    
    cin>>n;
    
    for(int i=1;i<=n;i++)
        cin>>v[i];
    
    cin>>nr_caz;
    
    for(int i=1;i<=nr_caz;i++)
    {
        cin>>caz;
        cin>>target;
        if(caz == 0)
            cout<<cautare_bin1(v, 1, n, target)<<'\n';
        else
            if(caz == 1)
                cout<<cautare_bin2(v, 1, n, target)<<'\n';
            else
                cout<<cautare_bin3(v, 1, n, target)<<'\n';
    }
}