#include <fstream>

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

int n,v[100010],l,r,mid,k,q,t,x;

int main()
{
    fin >> n;

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

    fin >> q;

    while(q--)
    {
        fin >> t >> x;

        if(t == 0)
        {
            l = 1;
            r = n;
            k = 0;
            while(l <= r)
            {
                mid = (l+r)/2;

                if(v[mid] == x)
                {
                    k = mid;
                    l = mid + 1;
                }

                else if(v[mid] > x)
                {
                    r = mid - 1;
                }

                else l = mid + 1;
            }

            if(k == 0) fout << -1 << '\n';
            else fout << k << '\n';
        }

        else if(t == 1)
        {
            l = 1;
            r = n;
            k = 0;

            while(l <= r){
                mid = (l + r) / 2;

                if(v[mid] <= x){
                    k = mid;
                    l = mid + 1;
                }

                else r = mid - 1;
            }

            fout << k << '\n';
        }

        else if(t == 2)
        {
            l = 1;
            r = n;
            k = 0;

            while(l <= r){
                mid = (l + r) / 2;

                if(v[mid] >= x){
                    k = mid;
                    r = mid - 1;
                }

                else l = mid + 1;
            }

            fout << k << '\n';
        }
    }

    return 0;
}