#include <fstream>

using namespace std;

         int a[100000],b[200000],t[100000];
int main()
{
    int i,n,m,st,dr,mij,j,r,ok,q,jmax,x,nr;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
        fin >> n;
    for(i = 1;i<=n;i++) { fin >> a[i]; t[a[i]]++;}
    fin >> m; m*=2;
        for(i = 1;i<=m;i++) fin >> b[i];
        //fout << m*2<<" ";

    for (i = 2;i<=m;i+=2)
    {
            x = b[i];
        if (b[i-1] == 0)
            {   jmax = -1;
            st = 1; dr = n;
                while(st < dr )
                {

                    mij = (st+dr)/2;
                      //  if ((st + dr) % 2 != 0 ) mij++;

                        if (a[mij] < x) st = mij+1;
                        else if (a[mij] > x) dr = mij-1;
                        else if (a[mij] == x) {j = mij; if(j > jmax) jmax = j; st = j;}


                }
            fout << jmax<<"\n";

            }
      else if (b[i-1] == 1)
            {
                    st = 1; dr = n; nr = 0;
                        while(st < dr )
                        {

                            mij = (st+dr)/2;
                       // if ((st + dr) % 2 != 0 ) mij++;

                        if (a[mij] <= x) { st = mij+1; j = mij; if(j > nr) nr = j;}
                        else if (a[mij] > x) dr = mij-1;
                        }
                    fout << nr <<"\n";


            }
        else if (b[i-1] == 2)
        {

                st = 1; dr = n; ok = 100001;
                        while(st < dr )
                        {

                            mij = (st+dr)/2;
                      //  if ((st + dr) % 2 != 0 ) mij++;

                        if (a[mij] < x)  st = mij+1;
                        else if (a[mij] >= x) {dr = mij-1;j = mij; if(j < ok) ok = j;}
                        }
                    fout << ok <<"\n";

        }

    }



   fin.close();
   fout.close();
    return 0;
}