#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int a[100001];
int n,cerinta,x,lg;
int cautbin1(int x,int lg)
{
   int i;
   for(i=0;lg!=0;lg=lg>>1)
     if(i+lg<n && x>=a[i+lg])
       i=i+lg;
    if(a[i]==x)
      return i+1;
    else
      return -1;
}
int cautbin2(int x,int lg)
{
   int i;
   for(i=0;lg!=0;lg=lg>>1)
     if(i+lg<n && x>=a[i+lg])
       i=i+lg;
      return i+1;
}
int cautbin3(int x,int lg)
{
    int i;
    for(i=n-1;lg!=0;lg=lg>>1)
       if(i-lg>=0 && x<=a[i-lg])
        i=i-lg;
    return i+1;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
      cin>>a[i];
    int q;
    cin>>q;
    for(lg=1;lg<=n;lg=(lg<<1));
    for(int i=0;i<q;i++)
    {
        cin>>cerinta>>x;
        if(cerinta==0)
          cout<<cautbin1(x,lg)<<'\n';
        else
          if(cerinta==1)
            cout<<cautbin2(x,lg)<<'\n';
        else
         cout<<cautbin3(x,lg)<<'\n';
    }
    return 0;
}