#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include<string>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, i, j, m,  b, a[100005], x, y, k, o;
int main()
{   f>>n;
    for (i=1; i<=n; ++i) f>>a[i];
    f>>m;
    while(m--)
    {   f>>o>>b;
        if (o==0)
        {   int x=1, y=n, k=0;
            while(x<=y)
            {   int m=(x+y)/2;
                if(a[m]<=b) x=m+1;  else y=m-1;
            }
            if (a[y]!=b) y=-1;
            g<<y<<'\n';
        }
        else if (o==1)
            {   int x=1, y=n, k=0;
                while(x<=y)
                {   int m=(x+y)/2;
                    if(a[m]<=b)  x=m+1; else y=m-1;
                }
                g<<y<<'\n';
            }
            else if (o==2)
                {   int x=1, y=n, k=0;
                    while(x<=y)
                    {   int m=(x+y)/2;
                        if(a[m]>=b)  y=m-1; else x=m+1;
                    }
                    g<<x<<'\n';
                }
    }
    g.close();  return 0;
}