Simulation - Concursul Național de Informatică 2024 | concurs

Andor este o planetă foarte foarte îndepărtată de planeta noastră. Totuși, oamenii și andorenii (locuitorii planetei Andor) au foarte multe lucruri în comun. Unul dintre aceste lucruri este pasiunea pentru șah.

Andorenii nu se descurcă foarte bine cu organizarea evenimentelor, așadar te roagă pe tine să îi ajuți să organizezi un concurs de șah pentru copii mici. Însă, andorenii nu au stabilit o limită maximă de vârstă pentru a considera un jucător să fie copil. Tu ai posibilitatea să o alegi.

Se știe că sunt $N$ participanți la acest concurs, pentru fiecare cunoști următoarele două lucruri:

• Cât de bun este jucătorul la șah ($1$ e cel mai slab scor, $10^9$ e cel mai bun scor);
• Vârsta pe care o are.

Tu ai favoriți la acest concurs, așadar ai vrea să răspunzi la $Q$ întrebări de forma: Dacă limita de vârsta ar fi de $t$ ani, cine ar câștiga concursul?

Cerință

Se dă $N$ și două șiruri $s_1, s_2, \dots s_N$ și $v_1, v_2, \dots v_N$. De asemena, se dă $Q$ și cele $Q$ interogări. Află răspunsul pentru fiecare întrebare.

Date de intrare

Pe prima linie a fișierului de intrare concurs.in se află numărul $N$. Pe a doua linie se află șirul $s_1, s_2, \dots s_N$. Pe a treia linie se află șirul $v_1, v_2, \dots v_N$. Pe a treia linie se află numărul $Q$ și pe următoarele $Q$ linii se află câte un număr $t$ pe fiecare linie.

Date de ieșire

Să se afișeze în fișierul concurs.out $Q$ linii. A $i$-a linie fiind răspunsul pentru a $i$-a întrebare.

Restricții și precizări

• $2 \leq N, Q \leq 200 \ 000$
• $1 \leq s_i, v_i, t \leq 10^9$
• Unitatea de timp folosită pe planeta Andor este diferită față de unitatea de timp folosită pe Terra, așadar participanții pot avea foarte foarte mulți ani.
• Se garantează că valorile șirului $s$ sunt distincte!
• Se garantează că pentru fiecare întrebare, există cel puțin un participant care poate participa la concurs

Exemplu

concurs.in

7
10 2 8 3 6 4 7
8 2 10 1 5 4 8
12
1
2
3
4
5
6
7
8
9
10
11
12

concurs.out

4
4
4
6
5
5
5
1
1
1
1
1

Explicație

Dacă limita de vârstă ar fi de $4$ ani, atunci particpanții ar fi cei cu numerele $2$, $4$, $6$. Scorurile lor fiind $2$, $3$, $4$. Deci, câștigătorul ar fi al $6$-lea participant.

Dacă limita de vârstă ar fi de $10$ ani, ar concura toți cei $N$ participanți. Așadar, câștigătorul ar fi primul participant (are scorul $10$).