#include <cstdio>
        using namespace std;
        int a[100001], n;
        int cb0 (int x)
        {
            int st=1, dr=n, m=(st+dr)/2;
            while (st<dr)
            {
                if (a[m]<x) st=m+1;
                else dr=m-1;
                m=(st+dr)/2;
            }
            while (a[m]==x) m++;
            if (a[m-1]==x) return m-1;
            else return -1;
        }
        int cb1 (int x)
        {
            int st=1, dr=n, m=(st+dr)/2;
            while (st<dr)
            {
                if (a[m]<x) st=m+1;
                else dr=m-1;
                m=(st+dr)/2;
            }
            while (a[m]<=x && m<=n) m++;
            return m-1;
        }
        int cb2 (int x)
        {
            int st=1, dr=n, m=(st+dr)/2;
            while (st<dr)
            {
                if (a[m]<x) st=m+1;
                else dr=m-1;
                m=(st+dr)/2;
            }
            while (a[m]>=x && m>=1) m--;
            return m+1;
        }
        int main()
        {
            int t, i, p, x;
            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",&t);
            for (i=1; i<=t; i++)
            {
                scanf("%d%d",&p,&x);
                if (p==0) printf("%d\n",cb0(x));
                if (p==1) printf("%d\n",cb1(x));
                if (p==2) printf("%d\n",cb2(x));
            }
            return 0;
        }