#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int m,n,v[10001],x,y;
int bs(int x)
{
    int L=1,R=n,poz=-1;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(x==v[mid])
        {
            L=mid;
            if(L==n-1) return L;
            poz=mid;
        }
        else if(x<v[mid]) R=mid-1;
        else L=mid+1;
    }
    return poz;
}
int bs1(int x)
{
    int L=1,R=n,poz;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(x==v[mid])
        {
            R=mid;
            poz=mid;
        }
        else if(x<v[mid]) R=mid-1;
        else L=mid+1;
    }
    return poz;
}
int main()
{
    ios::sync_with_stdio(false);
    f>>n;
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        if(x==0 || x==1) g<<bs(y)<<'\n';
        else g<<bs1(y)<<'\n';
    }
    return 0;
}