#include <fstream>
using namespace std;

/////////////////////////////////////

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

const int NMAX = 1e5 + 1;

int v[NMAX] , n , q , op , x;

//////////////////////////////////////////////

int main()
{

    cin >> n;

    for(int i = 1 ; i <= n ; i++) cin >> v[i];

    cin >> q;

    while(q--){

        cin >> op >> x;

        if(!op){

            int ans = -1, st = 1 , dr = n;

            while(st <= dr){

                int mij = (st+dr)/2;

                if(v[mij] <= x){

                    if(v[mij] == x) ans = mij;
                    st = mij + 1;

                }else dr = mij-1;

            }

            cout << ans << '\n';

            continue;

        }

        if(op&1){

            int ans = -1, st = 1 , dr = n;

            while(st <= dr){

                int mij = (st+dr)/2;

                if(v[mij] <= x){

                    ans = mij;
                    st = mij + 1;

                }else dr = mij-1;

            }

            cout << ans << '\n';

            continue;

        }

        int ans = -1, st = 1 , dr = n;

        while(st <= dr){

            int mij = (st+dr)/2;

            if(v[mij] >= x){

                ans = mij;
                dr = mij-1;

            }else st = mij + 1;

        }

        cout << ans << '\n';

    }

    return 0;
}