După descoperirea ruinelor unei cetăţi medievale, arheologii au hotărât restaurarea acesteia, începând cu zidul principal. Acesta este format din N piloni, fiecare cu lăţimea de 1 metru, aşezaţi unul lângă altul (lipiţi). Se cunoaşte înălţimea, în metri, a fiecărui pilon dar, din păcate, nu toţi mai sunt acum la acelaşi nivel.
Pentru restaurarea zidului, arheologii dispun de cărămizi care au lăţimea de câte 1 metru şi lungimi variabile, exprimate în metri. Sunt disponibile oricâte cărămizi, de oricare lungime. Considerăm că toate cărămizile disponibile şi toţi pilonii care alcătuiesc zidul au aceeaşi grosime, de 1 metru.
Restaurarea constă în două etape:
- în prima etapă, toţi pilonii cu înălţimea mai mare sau egală cu H se retează, aducându-se astfel la înălţimea H, ceilalţi, mai scunzi, păstrându-şi înălţimea iniţială;
- în a doua etapă se aduc toţi pilonii la aceeaşi înălţime, umplându-se golurile dintre ei cu cărămizi, astfel încât zidul să devină compact; din motive neînţelese, arheologii vor aşeza cărămizile “culcate”, fiecare dintre acestea ocupând, eventual, spaţiul aflat deasupra mai multor piloni.
Arheologii au analizat situaţia, independent, pentru Q valori posibile ale lui H.
Cerinţă
Pentru fiecare dintre cele Q valori alese pentru înălţimea H, se cere să se determine numărul minim de cărămizi necesare restaurării zidului, independent, pornind de la înălţimile iniţiale ale pilonilor.
Date de intrare
Fişierul restaurare.in conţine pe prima linie, numărul N de piloni. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând înălţimile iniţiale ale pilonilor, în ordine, de la stânga la dreapta. Pe linia a treia se află numărul natural Q, reprezentând numărul de valori posibile pentru înălţimea H. Pe a patra linie se află Q numere naturale, separate prin câte un spaţiu, reprezentând valorile posibile ale lui H.
Date de ieşire
Fişierul restaurare.out conţine Q numere, câte unul pe linie, reprezentând numărul minim de cărămizi necesare restaurării pentru fiecare dintre înălţimile H, în ordinea în care acestea apar în fişierul de intrare.
Restricţii
• 1 ≤ N ≤ 100000
• Înălţimea fiecărui pilon este un număr natural din intervalul [1,100000]
• 1 ≤ Q ≤ 100000
• 1 ≤ H ≤ valoarea maximă dintre înălţimile iniţiale ale pilonilor
• Pentru 35% dintre teste N ≤ 1000, iar pentru alte 40% dintre teste Q=1.
Exemple
restaurare.in
restaurare.out
Explicaţii
5
4 3 2 4 2
3
1 4 3
0
4
2
Forma iniţială a zidului:
Pentru H=1 toţi pilonii au aceeaşi înălţime, deci nu mai este necesară nicio cărămidă, pentru H=4, sunt necesare 4 cărămizi, zidul având, după restaurare structura din fig. a, iar pentru H=3, sunt necesare 2 cărămizi, zidul având, după restaurare structura din fig. b.
