#include <bits/stdc++.h>

using namespace std;
int n,task,a[100005],m,x;
int poz; bool gasit;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
void Do1(); void Do2(); void Do3();
void CB(int s,int d,int x)
{
    if(s<=d && poz==0)
    {int m=(s+d)/2;
      if(a[m]==x) {gasit=1; poz=m;}
      else if(a[m]<x) CB(m+1,d,x);
      else  CB(s,m-1,x);
    }
}
void Read()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>a[i];
    fin>>m;
    for(int i=1;i<=m;i++)
    {
         fin>>task>>x;
         gasit=0; poz=0;
         CB(1,n,x);
         //fout<<gasit;
         if(task==0) Do1();
         else if(task==1) Do2();
         else Do3();

    }
}
void Do1()
{
    if(gasit==1)
    {
        while(a[poz]==x) poz++;
        poz--;
        fout<<poz<<"\n";
    }
    else fout<<-1<<"\n";
}
void CB2(int s,int d,int x)
{
 if(s<=d)
 {
     int m=(s+d)/2;
     if(s==d && a[s]<=x) poz=s;
     else if(a[m]>x)
        if(x>a[m-1]) poz=m;
        else CB2(s,m-1,x);
     else
         if(x<a[m+1]) poz=m;
         else  CB2(m+1,d,x);
 }
}
void Do2()
{ if(gasit==1)
{while(a[poz]==x) poz++;
  poz--;
fout<<poz<<"\n";
}
else {poz=0;CB2(1,n,x); fout<<poz<<"\n";}

}
void CB3(int s,int d,int x)
{
 if(s<=d)
 {  //1 1 3 4 5
     int m=(s+d)/2;
     if(s==d && a[s]>=x) poz=s;
     else if(a[m]>x)
        if(x>a[m-1]) poz=m;
        else CB3(s,m-1,x);
     else
         if(x<a[m+1]) poz=m+1;
         else  CB3(m+1,d,x);
 }
}

void Do3()
{
    if(gasit==1)
{while(a[poz]==x) poz--; poz++;
  fout<<poz<<"\n";
}
else {poz=0; CB3(1,n,x); fout<<poz<<"\n";}
}

int main()
{
    Read();
    return 0;
}