#include <iostream>
const int NMAX=1e5+5;

using namespace std;

int v[NMAX];

int main()
{
    int n,i,m;
    cin>>n;
    for(i=1;i<=n;i++) cin>>v[i];
    cin>>m;
    for(i=1;i<=m;i++)
    {
        int tip,x;
        cin>>tip>>x;
        if(tip==0)
        {
            int st=1,dr=n,mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x) st=mij+1;
                else dr=mij-1;
            }
            mij=(st+dr)/2;
            if(v[mij]>x) mij--;
            if(v[mij]==x) cout<<mij;
            else cout<<-1;
        }
        else if(tip==1)
        {
            int st=1,dr=n,mij;
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x) st=mij+1;
                else dr=mij;
            }
            mij=(st+dr)/2;
            if(v[mij]>x) mij--;
            cout<<mij;
        }
        else
        {
            int st=1,dr=n,mij;
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<x) st=mij+1;
                else dr=mij;
            }
            mij=(st+dr)/2;
            if(v[mij]<x) mij++;
            cout<<mij;
        }
        cout<<endl;
    }
    return 0;
}