#include <fstream>
#include <iostream>
using namespace std;

int poz,v[100000],x,nr;

void bin(int l,int r,int opt)
{
    int m;
    m=(l+r)/2;
    if(m==l)
        {
            if(opt==0 && x==v[m+1] && poz<m+1)
                poz=m+1;
            else if(opt==1 && x>=v[m+1] && poz<m+1)
                poz=m+1;
            return;
        }
    switch (opt)
        {
            case 0:
                {
                    if(x<v[m])
                        {
                            bin(l,m-1,opt);
                        }
                    else if(x>v[m])
                        {
                            bin(m+1,r,opt);
                        }
                    else
                        {
                            if(poz<m && v[m]==x)
                                poz=m;
                            bin(m,r,opt);
                        }
                    break;
                }
            case 1:
                {
                    if(x<v[m])
                        {
                            bin(l,m-1,opt);
                        }
                    else
                        {
                            if(poz<m && v[m]<=x)
                                poz=m;
                            bin(m,r,opt);
                        }
                    break;
                }
            case 2:
                {
                    if(x>v[m])
                        {
                            bin(m+1,r,opt);
                        }
                    else
                        {
                            if(poz>m && v[m]>=x)
                                poz=m;
                            bin(l,m,opt);
                        }
                    break;
                }
        }
}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n,m;
    in>>n;
    int i;
    for(i=0;i<n;i++)
        {
            in>>v[i];
        }
    in>>m;
    for(i=0;i<m;i++)
        {
            in>>nr>>x;
            if(nr==2)
                poz=n-1;
            else
                poz=-1;
            bin(0,n-1,nr);
            out<<poz+1<<"\n";
        }
    return 0;
}