#include <bits/stdc++.h>
#define mod 1999999973
using namespace std;
int x,n,p,a[100003],t,q;

void date()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
}

int main()
{
    date();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d %d",&t,&x);
            if(t==0)
              { p=upper_bound(a+1,a+n+1,x)-a-1;
                if (a[p]!=x) p=-1;
              }
            else if(t==1) p=upper_bound(a+1,a+n+1,x)-a-1;
            else p=lower_bound(a+1,a+n+1,x)-a;
        printf("%d\n",p);
    }

    return 0;

}