#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int n,m,x;
int X[NMAX+1];

void citire(void)
{
    fi>>n;
    for(int i=1; i<=n; i++)
        fi>>X[i];
}

int caut_bin_0(void)
{
    int lo=1,hi=n,mid,result=-1;
    while(lo<=hi)
    {
        mid=lo+(hi-lo)/2;
        if(X[mid]==x)
        {
            result=mid;
            lo=mid+1;
        }
        else
            if(X[mid]>x)
                hi=mid-1;
            else
                lo=mid+1;
    }
    return result;
}

int caut_bin_1(void)
{
    int lo=1,hi=n,mid,result=-1;
    while(lo<=hi)
    {
        mid=lo+(hi-lo)/2;
        if(X[mid]<=x)
        {
            result=mid;
            lo=mid+1;
        }
        else
            if(X[mid]>x)
                hi=mid-1;
            else
                lo=mid+1;
    }
    return result;
}

int caut_bin_2(void)
{
    int lo=1,hi=n,mid;
    while(lo<hi)
    {
        mid=lo+(hi-lo)/2;
        if(X[mid]>=x)
            hi=mid;
        else
            lo=mid+1;
    }
    return lo;
}

void rezolvare_query(void)
{
    int q;
    fi>>m;
    while(m--)
    {
        fi>>q>>x;
        if(q==0)
            fo<<caut_bin_0();
        else if(q==1)
            fo<<caut_bin_1();
        else
            fo<<caut_bin_2();
        fo<<"\n";
    }
}

int main()
{
    citire();
    rezolvare_query();
    fi.close();
    fo.close();
    return 0;
}