#include<bits/stdc++.h>

using namespace std;

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

int n , v[100001] , t , p , y , st , dr , poz , mij;

int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; i++)
        fin >> v[i];

    fin >> t;
    while(t--)
    {
        fin >> p >> y;
        if(p == 0)
        {
            poz = -1;
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] == y)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else if(v[mij] > y)
                {
                    dr = mij - 1;
                }
                else
                {
                    st = mij + 1;
                }
            }
            fout << poz << '\n';
        }
        else if(p == 1)
        {
            poz = -1;
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] <= y)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            fout << poz <<'\n';
        }
        else
        {
            poz = -1;
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] >= y)
                {
                    dr = mij - 1;
                    poz = mij;
                }
                else
                {
                    st = mij + 1;
                }
            }
            fout << poz <<'\n';
        }
    }
}