#include <iostream>//Cautare binara
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream f("cautbin.in");

int a[NMAX];
int n = 0, n2;
int x = 0;

int mij;//Mijloc
//Descirere
//input
//output
int CB0(int s, int f, int x) //s, f - limitele vectorului ; x - numarul cautat
{
    //Cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir

    if(s>f)
        return -1;
    else
    {
        mij = (s+f)/2;
        if(x == a[mij] && x < a[mij+1])
            return mij;
        if(x < a[mij])
            return CB0(s, mij - 1, x);
        else
            return CB0(mij + 1, f, x);
    }

}

int CB1(int s, int f, int x) //s, f - limitele vectorului ; x - numarul cautat
{
    //Cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir

    if(s>f)
        return -1;
    else
    {
        mij = (s+f)/2;
        if(x == a[mij] && x < a[mij-1])
            return mij;
        if(x < a[mij])
            return CB0(s, mij - 1, x);
        else
            return CB0(mij + 1, f, x);
    }

}

void Start()
{
    //Sirul cu numere
    f>>n;
    for(int i = 0; i < n; i++)
    {
        f>>a[i];
    }
    //Comenzile
    f>>n2;

    for(int i = 0; i < n2; i++)
    {
        int tip, numar; //Comanda si numarul
        f>>tip>>numar;
        if(tip == 0) cout<<CB0(0, n-1, numar)<<endl;
        if(tip == 1) cout<<CB1(0, n-1, numar)<<endl;
        //if(tip == 2) cout<<CB2(0, n-1, numar)<<endl;
    }
}

void Afisare()
{
    for(int i = 0; i < n; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    Start();
    //Afisare();
}