#include <fstream>

using namespace std;

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

int v[100001], n;

int Caut_Bin0 (int numar)
{
    int st = 1, dr = n, m;
        while(st < dr)
        {
            m = (st + dr) / 2;

            if(v[m] == numar && v[m+1] != numar)
                return m;

                if(v[m] <= numar)
                    st = m + 1;
                else
                    dr = m;
        }
        if(v[st] == numar)
            return st;
    return  -1;
}

int Caut_Bin1(int numar)
{
    int st = 1, dr = n, m;
        while(st < dr)
        {
            m = (st + dr) / 2;
                if(v[m] <= numar && v[m+1] != numar)
                    return m;
                if(v[m] <= numar)
                    st = m + 1;
                else
                    dr = m;
        }
}

int Caut_Bin2(int numar)
{
    int st = 1, dr = n, m;
        while(st < dr)
        {
            m = (st + dr) / 2;
                if(v[m] >= numar && v[m-1] != numar)
                    return m;
                if(v[m] >= numar)
                    dr = m;
                else
                    st = m+1;
        }
}

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

 int Q, x, y;
    fin >> Q;
        for(int i = 1; i<=Q; i++)
        {
            fin >> x >> y;
                if(x == 0)
                    fout << Caut_Bin0(y) << endl;
                else if(x == 1)
                    fout << Caut_Bin1(y) << endl;
                else
                    fout << Caut_Bin2(y) << endl;
        }


}