//cautare binara infoarena
//scris pe 3 decembrie 2019
#include <fstream>
using namespace std;
int cautareBinara0(int x, int a[], int n)
{
  int lo=0, hi=n, mid, pos=-1;
    while(lo<=hi)
    {
       mid=lo+(hi-lo)/2;
       if(a[mid]==x)
       {
         pos=mid;
         while(a[pos]==x)
            pos++;
         return pos-1;
       }
       else if(a[mid]<x)
         lo=mid+1;
       else
         hi=mid-1;
    }
    return -1;
}
int cautareBinara2(int st, int a[], int dr, int x)
{
    int mid=(st+dr)/2;
    while(st<dr)
    {
       int mid=(st+dr)/2;
       if(a[mid]<=x)
         st=mid+1;
       else
         dr=mid;
    }
    mid=(st+dr)/2;
    return mid;
}
int cautareBinara1(int st, int a[], int dr, int x)
{
    int mid;
    while(st<dr)
    {
       mid=(st+dr)/2;
       if(a[mid]<x)
         st=mid+1;
       else
         dr=mid;
    }
    mid=(st+dr)/2;
    if(mid<x)
        mid++;
    return mid;
}
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int n, m, arr[100000]; fin>>n;
    for(int pas=0; pas<n; pas++)
       fin>>arr[pas];
    fin>>m;
    int x, op;
    for(int i=0; i<m; i++)
    {
       fin>>op>>x;
       switch(op)
       {
         case 2:
         {
           fout<<cautareBinara2(0, arr, n-1, x)<<endl;
           break;
         }
         case 1:
         {
           fout<<cautareBinara1(0, arr, n-1, x)<<endl;
           break;
         }
         case 0:///E bun: nu-l mai editam.
         {
          if(cautareBinara0(x, arr, n)==-1)
          {
              fout<<"-1";
              break;
          }
          fout<<cautareBinara0(x, arr, n)+1<<endl;
          break;
         }
       }
    }
    fin.close();
    fout.close();
    return 0;
}