#include <iostream>
#include <fstream>
using namespace std;
ifstream ka("cautbin.in");
ofstream ki("cautbin.out");
const int N_MAX = 100000;
int a[N_MAX + 2];
int n, m, c, x;

int cautare_dupa_x(int x, int c)
{
    int inc = 1, sf = n;
    while(inc < sf)
    {
        if(inc == sf-1)
        {
                if(c == 0)
                {
                    if(a[sf] == x)
                        return sf;
                    else if(a[inc] == x)
                        return inc;
                    else
                        return -1;
                }
                else if(c == 1)
                {
                    if(a[sf] <= x)
                        return sf;
                    else
                        return inc;
                }
                else
                {
                    if(a[inc] >= x)
                        return inc;
                    else
                        return sf;
                }
        }
        int mij = (inc+sf)/2;
        if(c == 2)
        {
            if(a[mij] >= x)
                sf = mij;
            else
                inc = mij;
        }
        else
        {
            if(a[mij] > x)
                sf = mij;
            else
                inc = mij;
        }
    }
}

int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
        ka >> a[i];
    a[n+1] = 0x7fffffff;
    ka >> m;
    for(int i =1; i <= m; i++)
    {
        ka >> c >> x;
        ki << cautare_dupa_x(x, c) << '\n';
    }
}