#include <fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long v[100001], n, m, i, p, x, y;
int s;
int zero (long k)
{x=1;
 y=n;
while (x<y)
{ if (v[x+(y-x)/2]==k){p=x+(y-x)/2+1;
                       while (v[p]==k) p++;
                       return p-1;
                       }
else
  if (v[x+(y-x)/2]>k)  y=x+(y-x)/2-1;
else
                     x=x+(y-x)/2+1;
}
if (v[x]==k)return x;
      else
            return -1;
}
int unu (long k)
{x=1;
 y=n;
while (x<=y)
if (v[x+(y-x)/2]>=k&&v[x+(y-x)/2-1]<=k)
if (v[x+(y-x)/2]==k)
return x+(y-x)/2;
else
return x+(y-x)/2-1;
else
if (v[x+(y-x)/2]>k)
y=x+(y-x)/2-1;
else
x=x+(y-x)/2+1;
}
 
int doi(long k)
{x=1;
 y=n;
while (x<=y)
if (v[x+(y-x)/2]>=k&&v[x+(y-x)/2-1]<=k)
if (v[x+(y-x)/2-1]==k)
return x+(y-x)/2-1;
else
return x+(y-x)/2;
else
if (v[x+(y-x)/2]>k)
y=x+(y-x)/2-1;
else
x=x+(y-x)/2+1;
}
int main()
{
long k;
f>>n;
for (i=1;i<=n;i++) f>>v[i];
f>>m;
for (i=1;i<=m;i++)
{f>>s>>k;
if (!s) g<<zero(k)<<"\n";
   else
        if (s==1) g<<unu(k)<<"\n";
            else
                 g<<doi(k)<<"\n";
}
f.close();
g.close();
return 0;
}