#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,a[100002],x,y;
int cb(int x)
{
    int j,i=n-1;
    for(j=0; i; i--)
        if(j+i<n and a[j+i]<=x)
            j+=i;
    return j;
}
int cbi(int x)
{
    int j,i=n-1;
    for(j=0; i; i--)
        if(j+i<n and a[j+i]<x)
            j+=i;
    return j;
}
int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        fin>>a[i];
    fin>>m;
    for(int i=0; i<m; i++)
    {
        fin>>x>>y;
        if(x==0)
        {
            if(y==a[n-1])
                fout<<n<<endl;
            else
                if(y>a[n-1])
                    fout<<-1<<endl;
                else
                    if(y<a[0])
                        fout<<-1<<endl;
                    else
                        fout<<cb(y)+1<<endl;
        }
        if(x==1)
        {
            fout<<cb(y)+1<<endl;
        }
        if(x==2)
        {
            fout<<cbi(y)+2<<endl;
        }
    }
    return 0;
}