#include<fstream.h> 
#include <iostream.h>    
ifstream f("cautbin.in");   
ofstream g("cautbin.out");     
int v[100001],n,m;     
int fct0(int x)   
{   
    int st=1,dr=n,mij;   
    while(st!=dr)   
         {   
         mij=(st+dr+1)/2;   
         if(x>=v[mij])   
            st=mij;   
         else dr=mij-1;   
         }   
    if(x==v[st])   
        return st;   
    return -1;   
}    
int fct1(int x)   
{   
    int st=1,dr=n,mij;   
    while(st!=dr)   
         {   
         mij=(st+dr+1)/2;   
         if(v[mij]<=x)   
            st=mij;   
         else dr=mij-1;   
         }   
    if(v[st]>x)   
        return st-1;   
    return st;   
}     
int fct2(int x)   
{   
    int st=1,dr=n,mij;   
    while(st!=dr)   
         {   
         mij=st+(dr-st)/2;   
         if(v[mij]>=x)   
            dr=mij;   
         else st=mij+1;   
         }   
    if(v[st]<x)   
        return st+1;   
    return st;   
}    
int main()   
{   
    int i,k,x;   
    f>>n;   
    for(i=1;i<=n;i++)   
    f>>v[i];   
    f>>m;   
    for(i=1;i<=m;i++)   
        {   
        f>>k>>x;   
        if(k==0)   
            g<<fct0(x)<<"\n";   
        else if(k==1)   
            g<<fct1(x)<<"\n";   
        else g<<fct2(x)<<"\n";   
        }   
    f.close();   
    g.close();   
    return 0;   
}