#include <fstream>
using namespace std;
int a[100000];
//1  3 3 3 5

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int q1(int x, int n)
{
    int i=1;
    int r=n;
    int m;
    int poz=-1;
   while(i<=r)
        {
       m=r+i/2;
        if(x==a[m])
            poz=m;
        if(x>=a[m])i=m+1;        else
        r=m-1;
}

return poz;
}
int q2(int x, int n)
{

    int i=1;
    int r=n;
    int m;
    int poz=-1;
   while(i<=r)
        {
       m=r+i/2;
        if(x>=a[m])
          poz=m;
        if(x>=a[m])i=m+1;
                else      r=m-1;
}

return poz;
}
int q3(int x,int n)
       {

    int i=1;
    int r=n;
    int m;
    int poz=-1;
   while(i<=r)
        {
       m=r+i/2;
        if(x<=a[m])
            poz=m;
        if(x<=a[m])r=m-1;
        else i=m+1;
        }

return poz;
       }
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
     int m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==0)
            cout<<q1(y,n);
        if(x==1)
            cout<<q2(y,n);
                   if(x==1)
            if(x==2)cout<<q3(y,n);
            cout<<'\n';
    }
}