#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m;
vector<int> vec;
int search0(int l,int r,int val)
{
    int max_pos = -1;
    while(l <= r)
    {
        int mid = l+(r-l)/2;
        if(vec[mid] == val) max_pos = max(max_pos,mid);
        if(val < vec[mid]) r = mid-1;
        else l = mid+1;
    }
    return max_pos;
}
int search1(int l,int r,int val)
{
    int max_pos = -1;
    while(l <= r)
    {
        int mid = l+(r-l)/2;
        if(vec[mid] <= val) max_pos = max(max_pos,mid);
        if(val < vec[mid]) r = mid-1;
        else l = mid+1;
    }
    return max_pos;
}
int search2(int l,int r,int val)
{
    int max_pos = 100001;
    while(l <= r)
    {
        int mid = l+(r-l)/2;
        if(vec[mid] >= val) max_pos = min(max_pos,mid);
        if(val > vec[mid]) l = mid+1;
        else r = mid-1;
    }
    return max_pos;
}
int main()
{
    fin>>n;
    int k;
    for(int i=0;i<n;i++)
    {
        fin>>k;
        vec.push_back(k);
    }
    fin>>m;
    int k2;
    for(int i=0;i<m;i++)
    {
        fin>>k>>k2;
        if(k == 0)
        {
            int ans = search0(0,n-1,k2);
            if(ans == -1) fout<<ans<<"\n";
            else fout<<ans+1<<"\n";
        }
        else if(k == 1) fout<<search1(0,n-1,k2)+1<<"\n";
        else if(k == 2) fout<<search2(0,n-1,k2)+1<<"\n";
    }
}