#include <bits/stdc++.h>

using namespace std;
int a[100002],n,q;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
}
int bsearch0 (int st, int dr, int x) {
    int mid;

    while (st <= dr) {
        mid = (st + dr) / 2;
        if (a[mid] <= x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    mid = (st + dr) / 2;

    if (a[mid] > x) mid --;
    if (a[mid] == x)
        return mid;
    return -1;
}
int bsearch1(int st,int dr,int x)
{
    int mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid]<=x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    mid = (st + dr) / 2;
    if(a[mid] > x) mid --;
    if(a[mid] == x)
        return mid;
    return -1;
}
int bsearch2(int st,int dr,int x)
{
    int mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid] < x)
            st=mid+1;
        else dr=mid-1;
    }
    mid=(st+dr)/2;
    if(a[mid]<x)mid++;
    return mid;

}
void rezolvare()
{
    int i,x,y;
    fin>>q;
    for(i=1;i<=q;i++)
    {
        fin>>x>>y;
        if(x==0)
            fout<<bsearch0(1,n,y)<<"\n";
        if(x==1)
                fout<<bsearch1(1,n,y)<<"\n";
        if(x==2)
                fout<<bsearch2(1,n,y)<<"\n";
    }
}
int main()
{
    citire();
    rezolvare();
    return 0;
}