#include <iostream>
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#define nmax 100000
int n,sir[nmax],m;

int cautare0(int x)
{int sol=-1,left=0,right=n;
while(left<=right)
{
    int mid=(left+right)/2;
    if(sir[mid]==x)
    {
        sol=mid;
        left=mid+1;
    }
    if(sir[mid]>x)
        right=mid-1;
    if(sir[mid]<x)
        left=mid+1;
}
return sol;
}

int cautare1(int x)
{
    int sol=-1,left=0,right=n;
while(left<=right)
{
    int mid=(left+right)/2;

    if(sir[mid]>x)
        right=mid-1;
    if(sir[mid]<=x)
        {left=mid+1;
        sol=mid;
        }
}

return sol;
}
int cautare2(int x)
{int sol=-1,mid,left=0,right=n;
    while(left<=right)
    {mid=left+(right-left)/2;
        if(sir[mid]>=x)
        {
            sol=mid;
            break;
        }
        if(sir[mid]<x)
            left=mid+1;

    }

    return sol;
}

int main()
{f>>n;
int i,j;
for(i=1;i<=n;i++)
    f>>sir[i];
f>>m;
for(i=1;i<=m;i++)
{
    int x,comanda;
    f>>comanda>>x;
    if(comanda==1)
        g<<cautare1(x)<<endl;
    if(comanda==0)
        g<<cautare0(x)<<endl;
    if(comanda==2)
        g<<cautare2(x)<<endl;
}



    return 0;
}