const maxn=100001;
type vector=array[0..maxn]of longint;
var n,i,m,x:longint;
    v:vector;
    tip:byte;
    p,q,r,s:longint;

function caut0:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if(s=x)and(v[r+1]<>x)then begin
                          caut0:=r;
                          exit;
                          end
                     else if x<s then q:=r-1
                                 else p:=r+1;
until p>q;
caut0:=-1;
end;

function caut1:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if(s<=x)and(x<v[r+1])then begin
                          caut1:=r;
                          exit;
                          end
                     else if x<s then q:=r-1
                                 else p:=r+1;
until p>q;
caut1:=-1;
end;

function caut2:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if(s>=x)and(x>v[r-1])then begin
                          caut2:=r;
                          exit;
                          end
                     else if x<=s then q:=r-1
                                  else p:=r+1;
until p>q;
caut2:=-1;
end;

begin
assign(input,'cautbin.in');
reset(input);
assign(output,'cautbin.out');
rewrite(output);
read(n);
v[0]:=-1;
//nu stiu daca citirea este mai rapida asa:
x:=n div 1000;
for i:=1 to x do
  begin
  m:=(i-1)*1000;
  read(
  v[m+1],v[m+2],v[m+3],v[m+4],v[m+5],v[m+6],v[m+7],v[m+8],v[m+9],v[m+10],
  v[m+11],v[m+12],v[m+13],v[m+14],v[m+15],v[m+16],v[m+17],v[m+18],v[m+19],v[m+20],
  v[m+21],v[m+22],v[m+23],v[m+24],v[m+25],v[m+26],v[m+27],v[m+28],v[m+29],v[m+30],
  v[m+31],v[m+32],v[m+33],v[m+34],v[m+35],v[m+36],v[m+37],v[m+38],v[m+39],v[m+40],
  v[m+41],v[m+42],v[m+43],v[m+44],v[m+45],v[m+46],v[m+47],v[m+48],v[m+49],v[m+50],
  v[m+51],v[m+52],v[m+53],v[m+54],v[m+55],v[m+56],v[m+57],v[m+58],v[m+59],v[m+60],
  v[m+61],v[m+62],v[m+63],v[m+64],v[m+65],v[m+66],v[m+67],v[m+68],v[m+69],v[m+70],
  v[m+71],v[m+72],v[m+73],v[m+74],v[m+75],v[m+76],v[m+77],v[m+78],v[m+79],v[m+80],
  v[m+81],v[m+82],v[m+83],v[m+84],v[m+85],v[m+86],v[m+87],v[m+88],v[m+89],v[m+90],
  v[m+91],v[m+92],v[m+93],v[m+94],v[m+95],v[m+96],v[m+97],v[m+98],v[m+99],v[m+100],
  v[m+101],v[m+102],v[m+103],v[m+104],v[m+105],v[m+106],v[m+107],v[m+108],v[m+109],v[m+110],
  v[m+111],v[m+112],v[m+113],v[m+114],v[m+115],v[m+116],v[m+117],v[m+118],v[m+119],v[m+120],
  v[m+121],v[m+122],v[m+123],v[m+124],v[m+125],v[m+126],v[m+127],v[m+128],v[m+129],v[m+130],
  v[m+131],v[m+132],v[m+133],v[m+134],v[m+135],v[m+136],v[m+137],v[m+138],v[m+139],v[m+140],
  v[m+141],v[m+142],v[m+143],v[m+144],v[m+145],v[m+146],v[m+147],v[m+148],v[m+149],v[m+150],
  v[m+151],v[m+152],v[m+153],v[m+154],v[m+155],v[m+156],v[m+157],v[m+158],v[m+159],v[m+160],
  v[m+161],v[m+162],v[m+163],v[m+164],v[m+165],v[m+166],v[m+167],v[m+168],v[m+169],v[m+170],
  v[m+171],v[m+172],v[m+173],v[m+174],v[m+175],v[m+176],v[m+177],v[m+178],v[m+179],v[m+180],
  v[m+181],v[m+182],v[m+183],v[m+184],v[m+185],v[m+186],v[m+187],v[m+188],v[m+189],v[m+190],
  v[m+191],v[m+192],v[m+193],v[m+194],v[m+195],v[m+196],v[m+197],v[m+198],v[m+199],v[m+200],
  v[m+201],v[m+202],v[m+203],v[m+204],v[m+205],v[m+206],v[m+207],v[m+208],v[m+209],v[m+210],
  v[m+211],v[m+212],v[m+213],v[m+214],v[m+215],v[m+216],v[m+217],v[m+218],v[m+219],v[m+220],
  v[m+221],v[m+222],v[m+223],v[m+224],v[m+225],v[m+226],v[m+227],v[m+228],v[m+229],v[m+230],
  v[m+231],v[m+232],v[m+233],v[m+234],v[m+235],v[m+236],v[m+237],v[m+238],v[m+239],v[m+240],
  v[m+241],v[m+242],v[m+243],v[m+244],v[m+245],v[m+246],v[m+247],v[m+248],v[m+249],v[m+250],
  v[m+251],v[m+252],v[m+253],v[m+254],v[m+255],v[m+256],v[m+257],v[m+258],v[m+259],v[m+260],
  v[m+261],v[m+262],v[m+263],v[m+264],v[m+265],v[m+266],v[m+267],v[m+268],v[m+269],v[m+270],
  v[m+271],v[m+272],v[m+273],v[m+274],v[m+275],v[m+276],v[m+277],v[m+278],v[m+279],v[m+280],
  v[m+281],v[m+282],v[m+283],v[m+284],v[m+285],v[m+286],v[m+287],v[m+288],v[m+289],v[m+290],
  v[m+291],v[m+292],v[m+293],v[m+294],v[m+295],v[m+296],v[m+297],v[m+298],v[m+299],v[m+300],
  v[m+301],v[m+302],v[m+303],v[m+304],v[m+305],v[m+306],v[m+307],v[m+308],v[m+309],v[m+310],
  v[m+311],v[m+312],v[m+313],v[m+314],v[m+315],v[m+316],v[m+317],v[m+318],v[m+319],v[m+320],
  v[m+321],v[m+322],v[m+323],v[m+324],v[m+325],v[m+326],v[m+327],v[m+328],v[m+329],v[m+330],
  v[m+331],v[m+332],v[m+333],v[m+334],v[m+335],v[m+336],v[m+337],v[m+338],v[m+339],v[m+340],
  v[m+341],v[m+342],v[m+343],v[m+344],v[m+345],v[m+346],v[m+347],v[m+348],v[m+349],v[m+350],
  v[m+351],v[m+352],v[m+353],v[m+354],v[m+355],v[m+356],v[m+357],v[m+358],v[m+359],v[m+360],
  v[m+361],v[m+362],v[m+363],v[m+364],v[m+365],v[m+366],v[m+367],v[m+368],v[m+369],v[m+370],
  v[m+371],v[m+372],v[m+373],v[m+374],v[m+375],v[m+376],v[m+377],v[m+378],v[m+379],v[m+380],
  v[m+381],v[m+382],v[m+383],v[m+384],v[m+385],v[m+386],v[m+387],v[m+388],v[m+389],v[m+390],
  v[m+391],v[m+392],v[m+393],v[m+394],v[m+395],v[m+396],v[m+397],v[m+398],v[m+399],v[m+400],
  v[m+401],v[m+402],v[m+403],v[m+404],v[m+405],v[m+406],v[m+407],v[m+408],v[m+409],v[m+410],
  v[m+411],v[m+412],v[m+413],v[m+414],v[m+415],v[m+416],v[m+417],v[m+418],v[m+419],v[m+420],
  v[m+421],v[m+422],v[m+423],v[m+424],v[m+425],v[m+426],v[m+427],v[m+428],v[m+429],v[m+430],
  v[m+431],v[m+432],v[m+433],v[m+434],v[m+435],v[m+436],v[m+437],v[m+438],v[m+439],v[m+440],
  v[m+441],v[m+442],v[m+443],v[m+444],v[m+445],v[m+446],v[m+447],v[m+448],v[m+449],v[m+450],
  v[m+451],v[m+452],v[m+453],v[m+454],v[m+455],v[m+456],v[m+457],v[m+458],v[m+459],v[m+460],
  v[m+461],v[m+462],v[m+463],v[m+464],v[m+465],v[m+466],v[m+467],v[m+468],v[m+469],v[m+470],
  v[m+471],v[m+472],v[m+473],v[m+474],v[m+475],v[m+476],v[m+477],v[m+478],v[m+479],v[m+480],
  v[m+481],v[m+482],v[m+483],v[m+484],v[m+485],v[m+486],v[m+487],v[m+488],v[m+489],v[m+490],
  v[m+491],v[m+492],v[m+493],v[m+494],v[m+495],v[m+496],v[m+497],v[m+498],v[m+499],v[m+500],
  v[m+501],v[m+502],v[m+503],v[m+504],v[m+505],v[m+506],v[m+507],v[m+508],v[m+509],v[m+510],
  v[m+511],v[m+512],v[m+513],v[m+514],v[m+515],v[m+516],v[m+517],v[m+518],v[m+519],v[m+520],
  v[m+521],v[m+522],v[m+523],v[m+524],v[m+525],v[m+526],v[m+527],v[m+528],v[m+529],v[m+530],
  v[m+531],v[m+532],v[m+533],v[m+534],v[m+535],v[m+536],v[m+537],v[m+538],v[m+539],v[m+540],
  v[m+541],v[m+542],v[m+543],v[m+544],v[m+545],v[m+546],v[m+547],v[m+548],v[m+549],v[m+550],
  v[m+551],v[m+552],v[m+553],v[m+554],v[m+555],v[m+556],v[m+557],v[m+558],v[m+559],v[m+560],
  v[m+561],v[m+562],v[m+563],v[m+564],v[m+565],v[m+566],v[m+567],v[m+568],v[m+569],v[m+570],
  v[m+571],v[m+572],v[m+573],v[m+574],v[m+575],v[m+576],v[m+577],v[m+578],v[m+579],v[m+580],
  v[m+581],v[m+582],v[m+583],v[m+584],v[m+585],v[m+586],v[m+587],v[m+588],v[m+589],v[m+590],
  v[m+591],v[m+592],v[m+593],v[m+594],v[m+595],v[m+596],v[m+597],v[m+598],v[m+599],v[m+600],
  v[m+601],v[m+602],v[m+603],v[m+604],v[m+605],v[m+606],v[m+607],v[m+608],v[m+609],v[m+610],
  v[m+611],v[m+612],v[m+613],v[m+614],v[m+615],v[m+616],v[m+617],v[m+618],v[m+619],v[m+620],
  v[m+621],v[m+622],v[m+623],v[m+624],v[m+625],v[m+626],v[m+627],v[m+628],v[m+629],v[m+630],
  v[m+631],v[m+632],v[m+633],v[m+634],v[m+635],v[m+636],v[m+637],v[m+638],v[m+639],v[m+640],
  v[m+641],v[m+642],v[m+643],v[m+644],v[m+645],v[m+646],v[m+647],v[m+648],v[m+649],v[m+650],
  v[m+651],v[m+652],v[m+653],v[m+654],v[m+655],v[m+656],v[m+657],v[m+658],v[m+659],v[m+660],
  v[m+661],v[m+662],v[m+663],v[m+664],v[m+665],v[m+666],v[m+667],v[m+668],v[m+669],v[m+670],
  v[m+671],v[m+672],v[m+673],v[m+674],v[m+675],v[m+676],v[m+677],v[m+678],v[m+679],v[m+680],
  v[m+681],v[m+682],v[m+683],v[m+684],v[m+685],v[m+686],v[m+687],v[m+688],v[m+689],v[m+690],
  v[m+691],v[m+692],v[m+693],v[m+694],v[m+695],v[m+696],v[m+697],v[m+698],v[m+699],v[m+700],
  v[m+701],v[m+702],v[m+703],v[m+704],v[m+705],v[m+706],v[m+707],v[m+708],v[m+709],v[m+710],
  v[m+711],v[m+712],v[m+713],v[m+714],v[m+715],v[m+716],v[m+717],v[m+718],v[m+719],v[m+720],
  v[m+721],v[m+722],v[m+723],v[m+724],v[m+725],v[m+726],v[m+727],v[m+728],v[m+729],v[m+730],
  v[m+731],v[m+732],v[m+733],v[m+734],v[m+735],v[m+736],v[m+737],v[m+738],v[m+739],v[m+740],
  v[m+741],v[m+742],v[m+743],v[m+744],v[m+745],v[m+746],v[m+747],v[m+748],v[m+749],v[m+750],
  v[m+751],v[m+752],v[m+753],v[m+754],v[m+755],v[m+756],v[m+757],v[m+758],v[m+759],v[m+760],
  v[m+761],v[m+762],v[m+763],v[m+764],v[m+765],v[m+766],v[m+767],v[m+768],v[m+769],v[m+770],
  v[m+771],v[m+772],v[m+773],v[m+774],v[m+775],v[m+776],v[m+777],v[m+778],v[m+779],v[m+780],
  v[m+781],v[m+782],v[m+783],v[m+784],v[m+785],v[m+786],v[m+787],v[m+788],v[m+789],v[m+790],
  v[m+791],v[m+792],v[m+793],v[m+794],v[m+795],v[m+796],v[m+797],v[m+798],v[m+799],v[m+800],
  v[m+801],v[m+802],v[m+803],v[m+804],v[m+805],v[m+806],v[m+807],v[m+808],v[m+809],v[m+810],
  v[m+811],v[m+812],v[m+813],v[m+814],v[m+815],v[m+816],v[m+817],v[m+818],v[m+819],v[m+820],
  v[m+821],v[m+822],v[m+823],v[m+824],v[m+825],v[m+826],v[m+827],v[m+828],v[m+829],v[m+830],
  v[m+831],v[m+832],v[m+833],v[m+834],v[m+835],v[m+836],v[m+837],v[m+838],v[m+839],v[m+840],
  v[m+841],v[m+842],v[m+843],v[m+844],v[m+845],v[m+846],v[m+847],v[m+848],v[m+849],v[m+850],
  v[m+851],v[m+852],v[m+853],v[m+854],v[m+855],v[m+856],v[m+857],v[m+858],v[m+859],v[m+860],
  v[m+861],v[m+862],v[m+863],v[m+864],v[m+865],v[m+866],v[m+867],v[m+868],v[m+869],v[m+870],
  v[m+871],v[m+872],v[m+873],v[m+874],v[m+875],v[m+876],v[m+877],v[m+878],v[m+879],v[m+880],
  v[m+881],v[m+882],v[m+883],v[m+884],v[m+885],v[m+886],v[m+887],v[m+888],v[m+889],v[m+890],
  v[m+891],v[m+892],v[m+893],v[m+894],v[m+895],v[m+896],v[m+897],v[m+898],v[m+899],v[m+900],
  v[m+901],v[m+902],v[m+903],v[m+904],v[m+905],v[m+906],v[m+907],v[m+908],v[m+909],v[m+910],
  v[m+911],v[m+912],v[m+913],v[m+914],v[m+915],v[m+916],v[m+917],v[m+918],v[m+919],v[m+920],
  v[m+921],v[m+922],v[m+923],v[m+924],v[m+925],v[m+926],v[m+927],v[m+928],v[m+929],v[m+930],
  v[m+931],v[m+932],v[m+933],v[m+934],v[m+935],v[m+936],v[m+937],v[m+938],v[m+939],v[m+940],
  v[m+941],v[m+942],v[m+943],v[m+944],v[m+945],v[m+946],v[m+947],v[m+948],v[m+949],v[m+950],
  v[m+951],v[m+952],v[m+953],v[m+954],v[m+955],v[m+956],v[m+957],v[m+958],v[m+959],v[m+960],
  v[m+961],v[m+962],v[m+963],v[m+964],v[m+965],v[m+966],v[m+967],v[m+968],v[m+969],v[m+970],
  v[m+971],v[m+972],v[m+973],v[m+974],v[m+975],v[m+976],v[m+977],v[m+978],v[m+979],v[m+980],
  v[m+981],v[m+982],v[m+983],v[m+984],v[m+985],v[m+986],v[m+987],v[m+988],v[m+989],v[m+990],
  v[m+991],v[m+992],v[m+993],v[m+994],v[m+995],v[m+996],v[m+997],v[m+998],v[m+999],v[m+1000]);
  end;
x:=x*1000;
for i:=1 to n mod 1000 do read(v[x+i]);
v[n+1]:=maxlongint;
read(m);
for i:=1 to m do
  begin
  read(tip,x);
  case tip of
    0:if x<>maxlongint then writeln(caut0)
                       else writeln(n);
    1:if x<>maxlongint then writeln(caut1)
                       else writeln(n);
    2:writeln(caut2);
    end;
  end;
close(output);
close(input);
end.