#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("cautbin.in");
ofstream fo("cautbin.out");
struct intrebari{int a,b;}intr[100000];
    int var1(int n, intrebari intr[],int x[],int i)
    {int st,dr,mijl;
    st=1;
    dr=n;
    while(st<=dr)
    {
      mijl=st+(dr-st+1)/2;
      if(x[mijl]==intr[i].b)
      {
       if(x[mijl]==x[mijl+1])
         while(x[mijl]==x[mijl+1])
               mijl++;
      return mijl;}
      else if(x[mijl]<intr[i].b)
             st++;
             else if(x[mijl]>intr[i].b)
                dr--;
    }
    return -1;
    }
int var2(int n, intrebari intr[],int x[],int i)
{int st,dr,mijl,poz[100000],j=1,pozmax=0;
    st=1;
    dr=n;
    while(st<=dr)
    {
      mijl=st+(dr-st+1)/2;
      if(x[mijl]<=intr[i].b)
      {
       if(x[mijl]==x[mijl+1])
         while(x[mijl]==x[mijl+1])
               mijl++;
         poz[j]=mijl;
         j++;
      }
      if(x[mijl]<intr[i].b)
      st++;
      if(x[mijl]>intr[i].b)
      dr--;
    }
    for(i=1;i<=j;i++)
    if(poz[i]>pozmax)
    pozmax=poz[i];
    return pozmax;
}
int var3(int n,intrebari intr[],int x[],int i)
{int st,dr,mijl,k,poz[100000],j=1,pozmin=10000000;
    st=1;
    dr=n;
    while(st<dr)
    {
      mijl=st+(dr-st+1)/2;
      if(x[mijl]>=intr[i].b)
      {
         poz[j]=mijl;
         j++;
      }
      if(x[mijl]>intr[i].b)
      dr--;
    }
    for(i=1;i<=j;i++)
    if(poz[i]<pozmin)
    pozmin=poz[i];
    if(pozmin>0)
    return pozmin-1;
    else return pozmin+1;
}
int main()
{int n,i,m,x[100001];
    f>>n;
    for(i=1;i<=n;i++)
    f>>x[i];
    f>>m;

    for(i=1;i<=m;i++)
    {
        f>>intr[i].a;
        f>>intr[i].b;
    }
    for(i=1;i<=m;i++)
    {
        if(intr[i].a==0)
            fo<<var1(n,intr,x,i)<<endl;
        if(intr[i].a==1)
            if(var1(n,intr,x,i)!=-1)
               fo<<var1(n,intr,x,i)<<endl;
            else fo<<var2(n,intr,x,i)<<endl;
        if(intr[i].a==2)
            fo<<var3(n,intr,x,i)<<endl;

    }
    return 0;
}