#include<fstream>
using namespace std;
int v[100001];
int caut1(int left,int right,int val)
{
    int mid,i;
    while (left <= right)
    {
        mid = left + (right - left)/2;

        if (val >= v[mid] )

            left = mid+1;

        else right = mid-1;
}
if(v[right]==val) return right;
    if(v[left]==val) return left;

    return -1;

}

int caut3(int left , int right , int val)
{
    int mid,i;
    while (left <= right)
    {

        mid = left + (right - left)/2;

        if (val > v[mid] )

            left = mid+1;

        if(val<=v[mid]) right = mid-1;
    }

    if(v[right]>=val) return right;
        else return left;

return i;
}

int caut2(int left,int right,int val)
{
    int mid;
    while(left<=right)
    {

        mid = left + (right-left)/2;
        if (val >= v[mid]) left = mid+1;
          else right = mid -1;
    }

    if(v[right] <= val) return right;
       else return left;
}
int main()
{

    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int i,n,val,T,tip;
    in>>n;
    for (i = 1 ; i<= n; i++ )
        in>>v[i];
    in>>T;
    for( ; T ; --T )
    {
        in>>tip>>val;
        if(tip==0) out<<caut1(1,n,val)<<"\n";
        if(tip==1) out<<caut2(1,n,val)<<"\n";
        if(tip==2) out<<caut3(1,n,val)<<"\n";
    }
    in.close();
    out.close();
    return 0;
}