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

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

int cautare_bin1(int v[],int left,int right,int target)
{
    int mid = (left + right) / 2;

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

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

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

int main()
{
    int v[100020],n,nr_caz,caz,target;
    
    in>>n;
    
    for(int i=1;i<=n;i++)
        in>>v[i];
    
    in>>nr_caz;

    for(int i=1;i<=nr_caz;i++)
    {
        in>>caz;
        in>>target;
        if(caz == 0)
            out<<cautare_bin1(v, 1, n, target)<<'\n';
        else
            if(caz == 1)
                out<<cautare_bin2(v, 1, n, target)<<'\n';
        else
            out<<cautare_bin3(v, 1, n, target)<<'\n';
    }
}