#include<fstream>
#include<algorithm>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,a[100005],m;

int main()
{
    int i,j,x,y,poz;
    fin>>n;
    for (i=1;i<=n;i++) fin>>a[i];
    fin>>m;
    for (j=1;j<=m;j++)
        {
         fin>>x>>y;
         if (x==0)
            {
                poz=upper_bound(a+1,a+n+1,y)-a;
                if (a[poz-1]==y) fout<<poz-1;
                else if (a[poz]==y) fout<<poz;
                else fout<<"-1";
            }
         if (x==1)
            {
               poz=upper_bound(a+1,a+n+1,y)-a;
               if (a[poz]==x) fout<<poz;
               else fout<<poz-1;
            }
         if (x==2)
            {
                poz=lower_bound(a+1,a+n+1,y)-a;
                if (a[poz]==y) fout<<poz;
                else
                    {
                        poz=upper_bound(a+1,a+n+1,y)-a;
                        fout<<poz;
                    }
            }
        fout<<"\n";
        }
    return 0;
}