#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001], QUERRY, q_num, x, n, maxx=-1;
int seek_for_x(int st, int dr, int x);
int seek_for_x_min(int st, int dr, int x);
int seek_for_x_max(int st, int dr, int x);

int main()
{
    in >> n;
    for(int i=1; i<=n; i++)
        in >> v[i];
    in >> QUERRY;
    for(int i=1; i<=QUERRY; i++)
    {
        in >> q_num >> x;
        if(q_num==0)
            maxx=0, out << seek_for_x(1,n,x) <<endl;
        else if(q_num==1)
            maxx=0,out << seek_for_x_min(1,n,x) << endl;
            else maxx=0,out << seek_for_x_max(1,n,x)<<endl;
    }




        return 0;
    }

int seek_for_x(int st, int dr, int x)
{
        int mij=(st+dr)/2;

        if(st>dr)
            return -1;
        else if(v[mij]==x)
            maxx=max(mij, maxx);
        if(v[mij]>=x)
            seek_for_x(st, mij-1,x);
        if(v[mij]<=x) seek_for_x(mij+1, dr,x);
        return maxx;
}

int seek_for_x_min(int st, int dr, int x)
{
        int mij=(st+dr)/2;

        if(st>dr)
            return -1;
        else if(v[mij]==x)
            maxx=max(mij, maxx);
        if(v[mij]>=x)
            seek_for_x(st, mij-1,x);
        if(v[mij]<=x) seek_for_x(st, mij-1,x);
        return maxx;
}
int seek_for_x_max(int st, int dr, int x)
{
        int mij=(st+dr)/2;

        if(st>dr)
            return -1;
        else if(v[mij]==x)
            maxx=min(mij, maxx);
        if(v[mij]>=x)
            seek_for_x(st, mij-1,x);
        if(v[mij]<=x) seek_for_x(st, mij-1,x);
        return maxx;
}