Fișierul intrare/ieșire	portofel2.in, portofel2.out	Sursă	Problema portofel
Autor	Cristian Frâncu | Isabela Coman	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.05 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	7.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Portofel 2 (clasa a 6-a)

Notă: Aceasta este o extensie a problemei Portofel, date la Concursul Marele Premiu (PACO) 2013. Singura diferență este că valorile bancnotelor pot avea valori până la 1 000 000 000 (în loc de 100 000).

Radu a primit de ziua lui un portofel foarte drăguț. Tatăl lui i-a pus în portofel, în ordinea crescătoare a bancnotelor o sumă de bani. Radu s-a bucurat foarte tare, gândindu-se că va păstra banii și îi va completa pentru a-și cumpăra un robot nou, el fiind pasionat de robotică. Astăzi se intoarce foarte bucuros de la o competiție la care a primit ca premiu un plic cu bani. În acesta erau mai multe bancnote asezate tot in ordinea crescătoare a valorilor.

El vrea să bage banii in portofel si procedează astfel: extrage un teanc de bancnote din banii primiti si îi inserează in portofel.

1. Care este numărul cel mai mare de bancnote de aceeași valoare, din portofel, după adăugarea celor primiți ca premiu.
2. Care este numărul minim de inserări astfel încât banii din portofel să rămână ordonați crescător?

Date de intrare

Pe prima linie a fișierului portofel2.in se va preciza numarul de bancnote n, pe care le are Radu deja in portofel iar pe următoarea linie valorile celor n bancnote, b1_i. Pe a treia linie se va preciza numărul de bancnote m primite ca premiu in plic, iar pe următoarea linie valorile celor m bancnote, b2_j.

Date de ieșire

În fișierul de ieșire portofel2.out se vor tipări, pe câte o linie, rezultatele celor 2 cerințe 1) și 2).

Restricții

• 1 ≤ n, m ≤ 100 000
• 1 ≤ b1_i, b2_j ≤ 1 000 000 000
• Pentru cerința 1 se acordă 20% din punctaj, iar pentru cerința 2 se acorda 80% din punctaj.

Exemplu