Problem 1464: restaurare

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, $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, numărul natural $Q$ , reprezentând numărul de valori posibile pentru înălțimea $H$ ;
pe a patra linie, $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 și precizări

$1 \le N, Q \le 100 \ 000$ ;
înălțimea fiecărui pilon este un număr natural din intervalul $[1, 100 \ 000]$ ;
$1 \le H \le \text{valoarea maximă dintre înălțimile inițiale ale pilonilor}$ ;
pentru $35\%$ dintre teste $N \le 1 \ 000$ , iar pentru alte $40\%$ dintre teste $Q=1$ .

Exemplu

restaurare.in

restaurare.out

0
4
2

Explicație

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, următoarea structură:

Pentru $H=3$ , sunt necesare $2$ cărămizi, zidul având, după restaurare, următoarea structură:

restaurare