#include <bits/stdc++.h>

using namespace std;

int a[100001],n,m;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int cb0(int x)
{
    if(x>a[n])
        return -1;
    if(x<a[1])
        return -1;
    int st,dr,mij,poz;
    st=1;
    dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(dr+st)/2;
        if(a[mij]==x)
        {
            poz=mij;
            st=mij+1;
        }
        else if(a[mij]<x)
            st=mij+1;
        else dr=mij-1;
    }
    return poz;
}
int cb1(int x)
{
    if(x<a[1])
        return 1;
    if(x>=a[n])
            return n;
    int st,dr,mij,poz;
    st=1;
    dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij] <= x)
        {
            poz=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return poz;
}
int cb2(int x)
{
    if(x<=a[1])
        return 1;
    int st,dr,mij,poz;
    st=1;
    dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x<=a[mij])
        {
            poz=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return poz;
}
int main()
{
    fin>>n;
    for(int i=1; i<=n;i++)
        fin>>a[i];
    fin>>m;
    int cer,elem;
    for(int i=1; i<=m;i++)
    {
        fin>>cer>>elem;
        if(cer==0)
            fout<<cb0(elem)<<"\n";
        else if(cer==1)
            fout<<cb1(elem)<<"\n";
        else fout<<cb2(elem)<<"\n";
    }
    return 0;
}