#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");

int a[100001],n,i,j;

int BS0(int x)
{
    int beg=1,end=n;
    int rez=-1;
    while(beg<=end)
    {
        int mid=beg+(end-beg)/2;
        if(a[mid]==x)
        {
            rez=mid;
            beg=mid+1;
        }
        else if(x<=a[mid])
            end=mid-1;
        else
            beg=mid+1;
    }
    return rez;
}

int BS1(int x)
{
    int beg=1,end=n;

    if(a[end]<=x)
        return n;
    if(a[beg]==x && a[beg+1]!=x)
        return beg;
    while(beg<=end)
    {
        int mid=beg+(end-beg)/2;
        if(a[mid]<x && x<a[mid+1])
        {
            return mid;
        }
        else if(x==a[mid] && x!=a[mid+1])
        {
            return mid;
        }
        else if(x==a[mid])
            beg=mid+1;
        else if(x<a[mid])
            end=mid-1;
        else
            beg=mid+1;
    }
    return -1;
}

int BS2(int x)
{
    int beg=1,end=n;

    if(a[beg]>=x)
        return beg;

    while(beg<=end)
    {
        int mid=beg+(end-beg)/2;
        if(a[mid]<x && x<a[mid+1])
        {
            return mid+1;
        }

        else if(x!=a[mid-1] && x==a[mid])
        {
            return mid;
        }
        if(x==a[mid])
            end=mid-1;
        else if(x<a[mid])
            end=mid-1;
        else
            beg=mid+1;
    }
    return -1;
}



int main()
{
    int t,s,b;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>s>>b;
        switch(s)
        {
            case 0:
            fout<<BS0(b);
            break;
            case 1:
            fout<<BS1(b);
            break;
            case 2:
            fout<<BS2(b);
            break;
        }
        fout<<"\n";
    }


}