#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int M,v[100005],N,y,z;
int cautarebinara(int cerinta,int x)
{
    int mijloc,st=0,dr=N-1,p=-1;
    if(cerinta==0)
    {
        while(st<=dr)
        {
            mijloc=(st+dr)/2;
            if(v[mijloc]==x)
                p=max(p,mijloc+1);
            if(v[mijloc]<=x)
                st=mijloc+1;
            else
                dr=mijloc-1;
        }
        return p;
    }
    if(cerinta==1)
    {
        while(st<=dr)
        {
            mijloc=(st+dr)/2;
            if(v[mijloc]<=x)
            {
                p=mijloc+1;
                st=mijloc+1;
            }
            if(v[mijloc]>x)
            {
                dr=mijloc-1;
            }
        }
        return p;
    }
    if(cerinta==2)
    {
        while(st<=dr)
        {
            mijloc=(st+dr)/2;
            if(v[mijloc]<x)
                st=mijloc+1;
            if(v[mijloc]>=x)
            {
                dr=mijloc-1;
                p=mijloc+1;
            }
        }
        return p;
    }
    return p;
}
int main()
{
    fin>>N;
    for(int i=0; i<N; i++)
    fin>>v[i];
    fin>>M;
    for(int i=0; i<M; i++)
    {
        fin>>y>>z;
        fout<<cautarebinara(y,z)<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}