using namespace std;
#include <iostream>
#include <stdio.h>
#include <fstream>

void search0(int stanga, int dreapta, int key, int *v);
void search1(int stanga, int dreapta, int key, int *v);
void search2(int stanga, int dreapta, int key, int *v);

int main(){

   int key, flag = 0, len = 0, nrintrebari;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    cin >> len;

    int v[len];

    for(int i = 0;i < len;i++){
        cin >> v[i];
    }

    cin >> nrintrebari;

    while(nrintrebari > 0){
        cin >> flag;
        cin >> key;
        if(flag == 0){
            search0(0,len, key,v);
        }
        else if( flag == 1){
            search1(0,len,key,v);
        }
        else if(flag == 2){
            search2(0,len,key,v);
        }
        nrintrebari--;
    }

    return 0;
}

void search0(int stanga, int dreapta, int key, int *v){
    int mijloc;
    while(dreapta > stanga + 1){
        mijloc = (dreapta + stanga)/2;

        if(v[mijloc] > key){
            dreapta = mijloc;
        }
        else{
            stanga = mijloc;
        }

    }

    if(v[stanga] != key)
       stanga = -1;
    else
        stanga++;

    cout<<stanga<<endl;
}

void search1(int stanga, int dreapta, int key, int *v){
    int mijloc;
    while(dreapta > stanga + 1){
        mijloc = (dreapta + stanga)/2;

        if(v[mijloc] > key){
            dreapta = mijloc;
        }
        else{
            stanga = mijloc;
        }
    }

    //if(v[stanga] != key)
     //   stanga++;
    cout<<stanga+1<<endl;
}

void search2(int stanga, int dreapta, int key, int *v){
    int mijloc;
    while(dreapta > stanga + 1){
        mijloc = (dreapta + stanga)/2;

        if(v[mijloc] > key){
            dreapta = mijloc;
        }
        else{
            stanga = mijloc;
        }
    }

    if(key != v[stanga])
        stanga++;

    cout<<stanga + 1<<endl;

}