#include<fstream>
using namespace std;

int n,a[100001];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");


int cbin0(int x)
{
    int s=1,d=n,m;
    while(s<d)
    {
        m=(s+d+1)/2;
        if (a[m]<=x) s=m;
        else d=m-1;
    }
    if(a[s]==x)return s;
    return -1;
}

int cbin1(int x)
{
    int s=1,d=n,m;
    while(s<d)
    {
        m=(s+d+1)/2;
        if (a[m]<=x) s=m;
        else d=m-1;
    }
    return s;
}

int cbin2(int x)
{
    int s=1,d=n,m;
    while(s<d)
    {
        m=(s+d)/2;
        if (a[m]>=x) d=m;
        else s=m+1;
    }
    return s;
}

int main()
{
    int i,t,k,x;
    fin>>n;
    for(i=1;i<=n;i++)
      fin>>a[i];
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>k>>x;
        switch(k)
        {
            case 0: fout<<cbin0(x)<<'\n'; break;
            case 1: fout<<cbin1(x)<<'\n'; break;
            case 2: fout<<cbin2(x)<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}