#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
int n,m,x,val,st,dr,mij,ans;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n;
    vector < int > v(n+1);
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    for(int q=1;q<=m;q++)
    {
        f>>x>>val;
        ans=-1;
        st=1,dr=n;
        if(x==0)
        {
            while(st<=dr)
            {
                mij=(st+dr)>>1;
                if(val<v[mij])
                    dr=mij-1;
                else
                {
                    if(v[mij]==val)
                        ans=mij;
                    st=mij+1;
                }
            }
        }
        else
        {
            if(x==1)
            {
               while(st<=dr)
               {
                   mij=(st+dr)>>1;
                   if(val<v[mij])
                        dr=mij-1;
                   else
                        ans=mij,
                        st=mij+1;
               }
            }
            else
            {
                while(st<=dr)
                {
                    mij=(st+dr)>>1;
                    if(val<=v[mij])
                        ans=mij,
                        dr=mij-1;
                    else
                        st=mij+1;

                }
            }
        }
        g<<ans<<'\n';
    }


    return 0;
}