/*

0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir

1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x

2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

*/



#include <fstream>

#include <iostream>

#define nmax 100005



using namespace std;



//ifstream fin("date.in");

ifstream fin("cautbin.in");

ofstream fout("cautbin.out");



int n, v[nmax], q, c, x;



int caut_binar(int st, int dr, int x){

    int mij;

    while(st <= dr){

        mij = (st + dr) / 2;

        if(x == v[mij])

            return mij;

        else if(x < v[mij])

            dr = mij - 1;

        else st = mij + 1;

    }

    return st;

}



int main(){



    fin >> n;

    for(int i = 1; i <= n; ++i)

        fin >> v[i];

    fin >> q;

    for(int i = 1; i <= q; ++i){

        fin >> c >> x;

        if(c == 0){

            int pos = caut_binar(1, n, x);

            while(v[pos] == v[pos + 1])

                pos++;

            if(v[pos] != x)

                pos = -1;

            fout << pos << '\n';

        }

        else if(c == 1){

            int pos = caut_binar(1, n, x);

            if(v[pos] != x)

                pos--;

            fout << pos << '\n';

        }

        else{

            int pos = caut_binar(1, n, x);

            if(v[pos] == x)

                while(v[pos] == v[pos - 1])

                    pos--;

            fout << pos << '\n';

        }

    }

    fin.close();

    fout.close();

    return 0;

}