#include <bits/stdc++.h>

using namespace std;

ifstream in ("cautbin.in");

ofstream out ("cautbin.out");

int v[100001];

int ct0bin(int val,int n)

{

    int pos=0;

    for(int msk=1<<20;msk>0;msk/=2)

        if(pos+msk<=n && v[pos+msk]<=val)

            pos+=msk;

        if(v[pos]==val)

            return pos;

        else

            return -1;

}

int ct1bin(int val,int n)

{

    int pos=0;

    for(int msk=1<<20;msk>0;msk/=2)

        if(pos+msk<=n && v[pos+msk]<=val)

            pos+=msk;

        if(v[pos]<=val)

            return pos;

}

int ct2bin(int val,int n)

{

    int pos=0;

    for(int msk=1<<20;msk>0;msk/=2)

        if(pos+msk<=n && v[pos+msk]<=val)

            pos+=msk;

        while(v[pos]==val)

            pos--;

        pos++;

            return pos;

}

int main()

{

     int n,i,m,c,x;

     in>>n;

     for(i=1;i<=n;i++)

        in>>v[i];

     in>>m;

     for(i=1;i<=m;i++)

     {

         in>>c>>x;

         if(c==0)

            out<<ct0bin(x,n)<<'\n';

         if(c==1)

            out<<ct1bin(x,n)<<'\n';

         if(c==2)

            out<<ct2bin(x,n)<<'\n';

     }



    return 0;

}