#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int v[100005], n, q;
void cautare_binara_0(int x, int st, int dr, int& poz)
{
    if(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]==x)
        {
            if(poz<mij) {poz=mij; cautare_binara_0(x, mij+1, dr, poz);}
        }
        else if(v[mij]<x) cautare_binara_0(x, mij+1, dr, poz);
        else cautare_binara_0(x, st, mij-1, poz);
    }
}
void cautare_binara_1(int x, int st, int dr, int& poz)
{
    if(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]==x)
        {
            poz=mij;
        }
        else if (v[mij]<x)
        {
            if(poz<mij) poz=mij;
            cautare_binara_1(x, mij+1, dr, poz);
        }
        else
        {
            cautare_binara_1(x, st, mij-1, poz);
        }

    }
}
void cautare_binara_2(int x, int st, int dr, int &poz)
{
    if(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]==x)
        {
            if(poz>mij) poz=mij;
            //if(mij-1>=st) cautare_binara_2(x, st, mij-1, poz);
        }
        else if(v[mij]<x) cautare_binara_2(x, mij+1, dr, poz);
        else
        {
            if(poz>mij) poz=mij;
            cautare_binara_2(x, st, mij-1, poz);
        }
    }

}
int main()
{
    f>>n;
    for(int i=0; i<n; i++)
        f>>v[i];
    f>>q;
    for(int i=0; i<q; i++)
    {
        int x, y;
        f>>x>>y;
        if(x==0)
        {
            int poz=-2;
            cautare_binara_0(y, 0, n-1, poz);
            g<<poz+1<<"\n";
        }
        else if (x==1)
        {
            int poz=-2;
            cautare_binara_1(y, 0, n-1, poz);
            g<<poz+1<<"\n";
        }
        else if (x==2)
        {
            int poz=n;
            cautare_binara_2(y, 0, n-1, poz);
            g<<poz+1<<"\n";
        }
    }
    return 0;
}