#include <iostream>
#include <fstream>

using namespace std;
 int a[100001];
int main()
{ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,i,lo,hi,x,nr,mid;
fin>>n;
for(i=1;i<=n;i++)
    fin>>a[i];
fin>>m;
    for(i=1;i<=m;i++)
        {fin>>nr>>x;
         if(nr==0)
            {lo=1;
             hi=n;
             while(lo<=hi)
                {mid=(lo+hi)/2;
                 if(a[mid]==x)
                    break;
                 else
                 if(a[mid]<x)
                    lo=mid+1;
                 else
                    hi=mid-1;
                }
             if(lo>hi)
                fout<<"-1"<<"\n";
             else
                {while(a[mid]==x)
                    mid++;
                fout<<--mid<<"\n";
                }
            }
          else
          if(nr==1)
            {lo=1;
             hi=n;
             mid=(lo+hi)/2;
             while(lo<hi)
                {
                 if(a[mid]==x)
                    break;
                 else
                 if(a[mid]<x)
                    lo=mid+1;
                 else
                    hi=mid-1;
                 mid=(lo+hi)/2;
                }
             if(lo>=hi)
                if(a[mid]>x)
                fout<<mid-1<<"\n";
                else
                fout<<mid<<"\n";
             else
                {while(a[mid]==x)
                    mid++;
                fout<<--mid<<"\n";
                }
            }
            else
             if(nr==2)
            {lo=1;
             hi=n;
             mid=(lo+hi)/2;
             while(lo<hi)
                {
                 if(a[mid]==x)
                    break;
                 else
                 if(a[mid]<x)
                    lo=mid+1;
                 else
                    hi=mid-1;
                 mid=(lo+hi)/2;
                }
             if(lo>=hi)
                {if(a[mid]<x)
                    fout<<mid+1<<"\n";
                 else
                    fout<<mid<<"\n";
                }
             else
                {while(a[mid]==x)
                    mid--;
                fout<<++mid<<"\n";
                }
            }
         }
    return 0;
}