#include <stdio.h>
#include <stdlib.h>

int v[100001];

int main()
{
    FILE *fin, *fout;
    int n, m, x, right, left, mid, pok, q, i;
    fin=fopen("cautbin.in", "r");
    fout=fopen("cautbin.out", "w");

    fscanf(fin, "%d", &n);
    for(i=1; i<=n; i++)
        fscanf(fin, "%d", &v[i]);

    fscanf(fin, "%d", &m);


    while(m--)
    {
        fscanf(fin, "%d%d", &q, &x);
        if(q==0)
        {
            pok=-1;
            left=1;
            right=n;
            while(left<=right)
            {
                mid=(left+right)/2;
                if(v[mid]<=x)
                {
                    left=mid+1;
                    pok=mid;
                }
                else right=mid-1;
            }
            if(pok!=-1 && v[pok]!=x)
                pok=-1;
            fprintf(fout, "%d\n", pok);
        }

        if(q==1)
        {
            left=1;
            right=n;
            pok=0;
            while(left<=right)
            {
                mid=(left+right)/2;
                if(v[mid]<=x)
                {
                    pok=mid;
                    left=mid+1;
                }
                else right=mid-1;
            }
            fprintf(fout, "%d\n", pok);
        }

        if(q==2)
        {
            left=1;
            right=n;
            pok=0;
            while(left<=right)
            {
                mid=(left+right)/2;
                if(v[mid]>=x)
                {
                    right=mid-1;
                    pok=mid;
                }
                else left=mid+1;
            }
            fprintf(fout, "%d\n", pok);
        }
    }


    fclose(fin);
    fclose(fout);
    return 0;
}