#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 100000

int n,m,v[Nmax],x,c;

int bin0(int lo, int hi, int val){

    int mid,poz=0;
    while(lo <= hi){
        mid=(lo+hi)/2;
    if(v[mid] == val){
        poz = mid;
        lo=mid+1;
    }
        else if(v[mid]<val) lo=mid+1;
        else if(v[mid] > val) hi=mid-1;
    }
    if(poz) return poz;
    return -1;
}

int bin1(int lo, int hi, int val){

    int mid,poz=0;
    while(lo<=hi){
        mid=(lo+hi)/2;
    if(v[mid] <= val){
        poz=mid;
        lo=mid+1;
    }

     else if(v[mid]<val) lo=mid+1;
        else if(v[mid] > val) hi=mid-1;
    }
    if(poz) return poz;
    return -1;
    }



int bin2(int lo, int hi, int val){

    int mid,poz=0;
    while(lo<=hi){
        mid=(lo+hi)/2;
    if(v[mid] >= val){
        poz=mid;
        hi=mid-1;
    }

     else if(v[mid]<val) lo=mid+1;
        else if(v[mid] > val) hi=mid-1;
    }
    if(poz) return poz;
    return -1;
    }



int main()
{
    in>>n;
    for(int i=1;i<=n;i++){
        in>>v[i];
    }
    in>>m;
    while(m){
        in>>c>>x;
        if(c == 0){
            out<<bin0(1,n,x)<<'\n';
        }
        if(c == 1){
            out<<bin1(1,n,x)<<'\n';
        }
        if(c == 2){
            out<<bin2(1,n,x)<<'\n';
        }
        m--;
    }
    return 0;
}