#include <iostream>
#include <fstream>
using namespace std;
int x,n,v[100001],i,y,m,quest,j;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int cautarebinara0(int lo, int hi, int x)
            {
                int mid=lo+(hi-lo)/2;
                if ((mid==hi) || (mid==lo))
                            {
                                if (v[mid]>x) mid--;
                                if (v[mid]<x) mid++;
                                if (v[mid]==x) return mid;
                                               else return -1;

                            }
                 else if (v[mid]<=x) return cautarebinara0 (mid+1, hi,x);
                                else return cautarebinara0 (lo, mid-1,x);
            }

int cautarebinara1(int lo, int hi, int x)
            {
                int mid=lo+(hi-lo)/2;
                if ((mid==hi) || (mid==lo))
                            {
                                if (v[mid]>x) mid--;
                                return mid;

                            }
                 else if (v[mid]<=x) return cautarebinara1 (mid+1, hi,x);
                                else return cautarebinara1 (lo, mid,x);
            }

int cautarebinara2(int lo, int hi,int x)
            {
                int mid=lo+(hi-lo)/2;

                if ((mid==hi) || (mid==lo))
                            {
                                if (v[mid]<x) mid++;
                                return mid;

                            }
                 else if (v[mid]<x) return cautarebinara2 (mid+1, hi,x);
                                else return cautarebinara2 (lo, mid,x);
            }
int main()
{

    f>>n;
    for (i=1;i<=n;i++) f>>v[i];
    f>>m;
    for (j=1;j<=m;j++)
          {
              f>>quest;
              f>>x;
              if (quest==0) g<<cautarebinara0(1,n,x)<<'\n';
              if (quest==1)
                  {
                      g<<cautarebinara1(1,n,x)<<'\n';
                  }
              if (quest==2)
                  {
                     g<<cautarebinara2(1,n,x)<<'\n';
                  }
          }
    return 0;
}