#include<iostream>
#include<fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int x,n,m,a,v[100001];

int fi(int x)
{
int     low=1;
int     high=n;
    while(1)
    {
            if (high-low==1) switch(a)
            {
                             case 0: return -1;
                             case 1: if (v[high]<=x) return high; else return low;
                             case 2: if (v[low]==x) return low; else return high;}
            int mid= (low+high)/2;
            if (v[mid]==x) {
                           if (a!=1)
                           {while(v[mid+1]==x) mid++; if (a==0) return mid;}
                           else while(v[mid-1]==x) mid--;}
            if(v[mid]>x) high=mid;
            else low=mid;
             
            }
     }

int main()
{
f>>n;
for(int i=1;i<=n; f>>v[i++]);
f>>m;
for(int i=1;i<=m;i++)
      {  f>>a>>x;
      g<<fi(x)<<"\n";}
    
    f.close();
    g.close();
    return 0;
    }