#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int main()
{
    int a[100001],*p,i,j,val,n,m;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
        {
            f>>j>>val;
            if(j==0)
               if(*find(a+1,a+n+1,val))
                  {
                      p=upper_bound(a+1,a+n+1,val);
                      g<<p-a-1<<'\n';
                  }
               else
                  g<<-1<<'\n';
            else
                if(j==1)
                  {
                      p=upper_bound(a+1,a+n+1,val);
                      if(*find(a+1,a+n+1,val))
                          g<<p-a-1<<'\n';
                      else
                          if(p-a>1)
                             g<<p-a-1<<'\n';
                          else
                             g<<p-a<<'\n';
                  }
                else
                    {
                        p=lower_bound(a+1,a+n+1,val);
                        if(*find(a+1,a+n+1,val))
                            g<<p-a<<'\n';
                        else
                            if(p-a>1)
                               g<<p-a-1<<'\n';
                            else
                               g<<p-a;
                    }
        }
    f.close();
    g.close();
    return 0;
}