#include <iostream>
#include <fstream>
#define NMAX 100000

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, q, v[NMAX+10];

int binSearch1(int val)
{   int st = 1, dr = n;
    while(st <= dr)
        {   int mij = (st + dr) / 2;
            if(val >= v[mij]) st = mij + 1;
            else dr = mij - 1;
        }
    return dr;
}

int binSearch2(int val)
{   int st = 1, dr = n;
    while(st <= dr)
        {   int mij = (st + dr) / 2;
            if(val > v[mij]) st = mij + 1;
            else dr = mij - 1;
        }
    return st;
}

int main()
{
    f >> n;
    for(int i=1; i<=n; i++) f >> v[i];
    f >> q;
    while(q--)
        {   int type, x;
            f >> type >> x;
            if(type == 0 || type == 1)
                {   int poz = binSearch1(x);
                    if(!type)
                        {   if(v[poz] != x) g << -1 << '\n';
                            else g << poz << '\n';
                        }
                    else g << poz << '\n';
                }
            else
                {   int poz = binSearch2(x);
                    g << poz << '\n';
                }
        }
    return 0;
}