Rezolvare PBinfo #4435

Pentru că se plictisește și este foarte inteligent, Radu l-a rugat pe prietenul lui, savantul Feder, să creeze o activitate care să-i pună mintea la încercare. Savantul Feder a adus N piese dreptunghiulare pe care sunt scrise numere naturale și le-a așezat pe masă în ordinea crescătoare a valorilor scrise pe ele, pe poziții consecutive, una lângă cealaltă. Apoi îi dă lui Radu, una câte una, alte M piese dreptunghiulare, pe care sunt scrise numere naturale, într-o ordine oarecare. Când Radu primește o piesă el trebuie să o așeze în șirul de pe masă pe cea mai mică poziție posibilă, astfel încât piesele din șir să rămână în ordine crescătoare. Evident, șirul de pe masă se modifică pe măsură ce Radu așază piesele în șir.

Cerința

Cunoscând șirul pieselor de pe masă, în ordinea în care sunt așezate, precum și cele M piese pe care le primește succesiv Radu, scrieți un program care să afișeze pentru fiecare dintre cele M piese poziția pe care aceasta este așezată în șir.

Date de intrare

Fișierul de intrare dominew.in conține pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, în ordine crescătoare, reprezentând valorile pieselor din șirul aflat inițial pe masă. Pe a treia linie se află numărul natural M. Pe cea de-a patra linie sunt M numere naturale, reprezentând valorile pieselor pe care le primește Radu, în ordinea în care acesta le primește. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire dominew.out va conține o singură linie pe care vor fi scrise M valori separate prin câte un spațiu, cea de a i-a valoare fiind poziția pe care este așezată în șirul de pe masă cea de a i-a piesă primită de Radu (1 ≤ i ≤ M).

Restricții și precizări

• 2 ≤ N ≤ 1.000.000
• 1 ≤ M ≤ 8.000
• Valorile scrise pe piese sunt numere naturale mai mici sau egale cu 1.000.000.000
• Pozițiile elementelor din șirul de pe masă sunt numerotate începând cu 1.
• Datorită testelor prea mari, nu au putut fi adăugate toate.

Exemplul 1:

dominew.in

6
2 5 5 9 10 11
3
5 1 12

dominew.out

2 1 9

Explicație

Inițial pe masă se află N=6 piese, în ordine crescătoare. 2 5 5 9 10 11. Radu primește M=3 piese.
Prima piesă are valoarea 5 și va fi așezată în șirul de pe masă pe poziția 2. Șirul va deveni 2 5 5 5 9 10 11.
A doua piesă are valoarea 1, va fi așezată în șirul de pe masă pe poziția 1. Șirul va deveni 1 2 5 5 5 9 10 11.
A treia piesă are valoarea 12 și va fi așezată pe poziția 9 în șirul de pe masă. Șirul va deveni 1 2 5 5 5 9 10 11 12.

Exemplul 2:

dominew.in

14
2 2 2 4 7 8 9 10 12 16 20 21 23 24
7
18 7 20 1 16 25 23

dominew.out

11 5 13 1 12 20 18

Explicație

După primele trei inserări, șirul va fi 2 2 2 4 7 7 8 9 10 12 16 18 20 20 21 23 24, valoarea 20 ajungând pe poziția 13.