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