#include<fstream>
using namespace std;
ifstream f("cautbin.in"); ofstream g("cautbin.out");
int v[100001];
int main()
{   int n,i,k,m;
    f>>n;
    for(i=1; i<=n; i++) f>>v[i];
    f>>k;
    while(k--)
    {   int t,x,st,dr;
        f>>t>>x;
        if(t==0)
        {   st=1; dr=n;
            while(st<=dr)
            {   m=(st+dr)/2;
                if(v[m]<=x) st=m+1; else dr=m-1;
            }
            m=(st+dr)/2;
            if(v[m]>x) m--;
            if(v[m]==x) g<<m<<"\n"; else g<<"-1\n";
        };
        if(t==1)
        {   st=1; dr=n;
            while(st<dr)
            {   m=(st+dr)/2;
                if(v[m]<=x) st=m+1; else dr=m;
            }
            //mid = (p + u) / 2;
            //if (v[mid] > x) mid--;
            //if (v[mid] == x) out << mid << '\n'; else out << -1 << '\n';
            m=(st+dr)/2;
            if(x<v[m]) m--;
            g<<m<<"\n";
        };
        if(t==2)
        {   st=1; dr=n;
            while(st<dr)
            {   m=(st+dr)/2;
                if(v[m]<x) st=m+1; else dr=m;
            }
            m=(st+dr)/2;
            if(v[m]<x) m++;
            g<<m<<"\n";
        };
    }
    g.close();
    return 0;
}
/*

#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int n, m, t, x, mid, p, u, v[100001];
int main()
{   in >> n;
    for (int i = 1; i <= n; i++) in >> v[i];
    in >> m;
    for (int i = 1; i <= m; i++)
    {   in >> t >> x;
        p = 1; u = n;
        if (t == 0)
        {   while (p <= u)
            {   mid = (p + u) / 2;
                if (v[mid] <= x) p = mid + 1;  else u = mid - 1;
            }
            mid = (p + u) / 2;
            if (v[mid] > x) mid--;
            if (v[mid] == x) out << mid << '\n'; else out << -1 << '\n';
        }
        if (t == 1)
        {  while (p < u)
            {   mid = (p + u) / 2;
                if (v[mid] <= x) p = mid + 1; else u = mid;
            }
            mid = (p + u) / 2;
            if (x < v[mid]) mid--;
            out << mid << '\n';
        }
        if (t == 2)
        {   while (p < u)
            {   mid = (p + u) / 2;
                if (v[mid] < x) p = mid + 1; else u = mid;
            }
            mid = (p + u) / 2;
            if (v[mid] < x) mid++;
            out << mid << '\n';
        }
    }
    out.close(); return 0;
}

*/