//
//  main.cpp
//  cautbin
//
//  Created by Andrada Minca on 05.11.2024.
//

#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,c,x,m,v[100005];
int up1(int x,int st)
{
    int dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(x==v[mij]&&v[mij+1]!=x) return mij;
        if(x>=v[mij]) st=mij+1;
        if(x<v[mij]) dr=mij-1;
    }
    return -1;
}
int up2(int x,int st)
{
    int dr=n;
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x==v[mij]&&v[mij+1]!=x) return mij;
        if(x>=v[mij]) st=mij+1;
        if(x<v[mij]) dr=mij-1;
    }
    return mij+1;
}
int up3(int x,int st)
{
    int dr=n;
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x==v[mij]&&v[mij-1]!=x) return mij;
        if(x>v[mij]) st=mij+1;
        if(x<=v[mij]) dr=mij-1;
    }
    return mij-1;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>c>>x;
        if(c==0)fout<<up1(x,1)<<'\n';
        if(c==1)fout<<up2(x,1)<<'\n';
        if(c==2)fout<<up3(x,1)<<'\n';
    }
    return 0;
}