#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001],n;
int cautb(int x)
{
    int i=1,pas=1<<16;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}
int cautb2(int x)
{
    int i=1,pas=1<<16;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<x)
            i+=pas;
        pas/=2;
    }
    return i+1;
}
int cautb0(int x)
{
    int i=1,pas=1<<16;
    while(pas!=0)
    {
        if(i+pas<=n && v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    if(v[i]==x)
        return i;
    else
        return -1;
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    int m,t,x,poz;
    in>>m;
    for(int i=0;i<m;i++)
    {
        in>>t>>x;
        if(t==0)
            out<<cautb0(x)<<"\n";
        else if (t==1)
            out<<cautb(x)<<"\n";
        else
            out<<cautb2(x)<<"\n";
    }
    return 0;
}