#include <bits/stdc++.h>

using namespace std;

int n , i , x , a[100005], m , dr , st , q , poz=-1 , mij;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
    f >> n ;
    for(i=1;i<=n;i++)f >> a[i];
    f >> m ;
    for(i=1;i<=m;i++){
        f >> q >> x ;
        poz=-1;
        if(q==0){
            dr=1;
            st=n;
            while(dr<=st){
                mij=(dr+st)/2;
                if(a[mij]<x)dr=mij+1;
                else if(a[mij]==x)poz=mij,dr=mij+1;
                else if(a[mij]>x)st=mij-1;
            }
            g << poz << '\n';
        }
        else if(q==1){
            dr=1;
            st=n;
            while(dr<=st){
                mij=(dr+st)/2;
                if(a[mij]<=x)poz=mij,dr=mij+1;
                else if(a[mij]>x)st=mij-1;
            }
            g << poz << '\n';
        }
        else if(q==2){
            dr=1;
            st=n;
            while(dr<=st){
                mij=(dr+st)/2;
                if(a[mij]>=x)poz=mij,st=mij-1;
                else if(a[mij]<x)dr=mij+1;
            }
            g << poz << '\n';
        }
    }
}