#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int arr[100001];
int main()
{
    int n,q,a,o=0,u=0,x;
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>arr[i];
    }
    in>>q;
    for(int i=1; i<=q; i++)
    {
        in>>a>>x;
        int l=1;
        int h=n;
        if(a==0)
        {
            while (l<h)
            {
                int mid=(l+h)/2;
                if(arr[mid]>x)
                    h=mid;
                else
                    l=mid+1;
            }
            if(arr[h-1]==x)
            {
                out<<h-1<<endl;
            }
            else
            {
                out<<-1<<endl;
            }

        }
        if(a==1){
        while (l<h)
            {
                int mid=(l+h)/2;
                if(arr[mid]>x)
                    h=mid;
                else
                    l=mid+1;
            }
                if(h==n){
                out<<n<<endl;
                }
                out<<h-1<<endl;
        }
        if(a==2){
         while (l<h)
            {
                int mid=(l+h)/2;
                if(arr[mid]>=x)
                    h=mid;
                else
                    l=mid+1;
            }

                out<<h<<endl;
        }
    }
    return 0;
}