//#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

vector<int>x;

int m,n,i,a,b;
int bsearch0(int p,int q,int r)
{
    int a;
    while(p<=q)
    {
        a=(p+q)/2;
        if(x[a]<=r) p=a+1;
        else q=a-1;
    }
    a=(p+q)/2;
    if(x[a]>r) a--;
    if(x[a]==r) return a;
    else return -1;
}

int bsearch1(int p,int q,int r)
{
    int a;
    while(p<q)
    {
        a=(p+q)/2;
        if(x[a]<=r) p=a+1;
        else q=a-1;
    }
    a=(q+p)/2;
    if(x[a]>r) a--;
    return a;
}
int bsearch2(int p,int q,int r)
{
    int a;
    while(p<q)
    {
        a=(p+q)/2;
        if(x[a]<r) p=a+1;
        else q=a-1;
    }
    a=(p+q)/2;
    if(x[a]<r) a++;
    return a;
}
int main()
{
    cin>>n;
    x.resize(n+1);
    for(i=1;i<=n;++i)
        cin>>x[i];
    cin>>m;
    while(m--)
    {
        cin>>a>>b;
        if(a==0) cout<<bsearch0(1,n,b)<<"\n";
        if(a==1) cout<<bsearch1(1,n,b)<<"\n";
        if(a==2) cout<<bsearch2(1,n,b)<<"\n";
    }
    return 0;
}