#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001];

int main()
{
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    int m,cerinta,x,pos_max,st,dr,mijloc;
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> cerinta >> x;
        switch(cerinta)
        {
            case 0:
                pos_max = -1;
                st = 1;
                dr = n;
                while(dr - st > 1)
                {
                    mijloc = (st + dr) /2;
                    if(v[mijloc] > x)
                    {
                        dr = mijloc;
                    }
                    else st = mijloc;
                }
                if(x == v[st])
                {
                    pos_max = st;
                }
                fout << pos_max << '\n';
                break;
            case 1:
                st = 1;
                dr = n;
                while(dr - st > 1)
                {
                    mijloc = (st + dr) /2;
                    if(v[mijloc] > x)
                    {
                        dr = mijloc;
                    }
                    else st = mijloc;
                }
                if(x >= v[st])
                {
                    pos_max = st;
                }
                fout << pos_max << '\n';
                break;
            case 2:
                st = n;
                dr = 1;
                while(st - dr > 1)
                {
                    mijloc = (st + dr) /2;
                    if(v[mijloc] > x)
                    {
                        dr = mijloc;
                    }
                    else st = mijloc;
                }
                if(x <= v[st])
                {
                    pos_max = st;
                }
                fout << pos_max;
                break;
        }
    }
    return 0;
}