#include <bits/stdc++.h>
using namespace std;
#define nmax 100000
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[nmax+5];

int main()
{
    int n,m;
    f>>n;
    for(int i=1;i<=n;++i)
        f>>v[i];
    f>>m;
    for(int i=1;i<=m;++i)
    {
        int cer,x;
        f>>cer>>x;
        int poz=-1,st=1,dr=n;
        if(cer==0){
            while(st<=dr){
                int mid=(st+dr)/2;
                if(v[mid]==x)poz=mid,st=mid+1;
                else if(v[mid]<x)st=mid+1;
                else dr=mid-1;
            }
        }
        else if(cer==1){
            while(st<=dr){
                int mid=(st+dr)/2;
                if(v[mid]<=x)poz=mid,st=mid+1;
                else dr=mid-1;
            }
        }
        else{
            while(st<=dr){
                int mid=(st+dr)/2;
                if(v[mid]>=x)poz=mid,dr=mid-1;
                else st=mid+1;
            }
        }
        g<<poz<<"\n";
    }
}