#include <cstdio>
#define N 100005
using namespace std;
int n,m;
int a[N];
int cautbin_0(int x)
{ int st,dr,p,mij;
st=1; dr=n; p=-1;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(a[mij]<x)st=mij+1;
    else if(a[mij]>x)dr=mij-1;
    else {
          p=mij;
          st=mij+1;
         }
    }
return p;
}
int cautbin_1(int x)
{ int st,dr,p,mij;
st=1; dr=n; p=0;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(a[mij]>x)dr=mij-1;
    else {
         p=mij;
         st=mij+1;
         }
    }
return p;
}
int cautbin_2(int x)
{ int st,dr,p,mij;
st=1; dr=n; p=0;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(a[mij]<x)st=mij+1;
    else {
          p=mij;
          dr=mij-1;
         }
    }
return p;
}
int main()
{ int i,x,op,poz;
freopen("cautbin.in","r",stdin); freopen("cautbin.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;++i)scanf("%d ",&a[i]);
scanf("%d\n",&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d\n",&op,&x);
        switch(op)
        {
        case 0:
            poz=cautbin_0(x);
            break;
        case 1:
            poz=cautbin_1(x);
            break;
        case 2:
            poz=cautbin_2(x);
            break;

        }
    printf("%d\n",poz);
    }
fclose(stdin);
fclose(stdout);
return 0;
}