#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
long n;
int x;
int v[100001];

long caut_bin1 (long n, int x, int *v)
{
    long left,mid,right;
    left=1;right=n;
    while (left<=right)
    {
        mid=(left+right)/2;
        if(v[mid]==x)
        {
            while(v[mid+1]==x)
                mid++;
            return mid;
        }
        else
            if(v[mid]<x)
            right=mid-1;
        else
           left=mid+1;
    }
        return -1;

}

long caut_bin2 (long n, int x, int *v)
{
    long left, mid,right;
    left=1; right=n;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(v[mid]>x)
            right=mid-1;
        else left=mid+1;
    }
    return right;
    }
long caut_bin3 (long n, int x, int *v)
{
    long left, mid, right;
    left=1; right=n;
    while(left<=right)
    {
        mid=(left+right)/2;
        if (v[mid]==x)
        {
           while(v[mid-1]==x)
            mid--;
            return mid;
        }
        else
            if(v[mid]>x)
            right=mid-1;
        else
            left=mid+1;
    }
    return mid;
    }

int main()
{
    long i,m;
    int c;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>c>>x;
        if (c==0)
            g<<caut_bin1(n,x,v)<<endl;
        else
            if(c==1)
            g<<caut_bin2(n,x,v)<<endl;
        else
            g<<caut_bin3(n,x,v)<<endl;
    }
    f.close();g.close();
    return 0;
}