== include(page="template/taskheader" task_id="towers") ==
Poveste și cerință...
Orașul _X_ este format din _N_ cladiri, aranjate de la vest la est și numerotate de la 1 la _N_. *Fiecare clădire are o înaltime diferită - un număr întreg, respectiv $h[~1~], h[~2~], .., h[~N~]$*.
Guvernul plănuiește să construiască un turn care să fie în rând cu celelalte clădiri (poate să fie construit înaintea primei clădiri, între oricare două clădiri sau după ultima cladire). Turnul va difuza mesaje catre cetățeni. *Înalțimea turnului trebuie să fie _H_, înălțime care trebuie să fie diferită de înălțimile celorlalte cladiri*.
Din cauza unor idei ciudate ale inginerilor, turnul va putea difuza semnal doar către partea de vest (doar către primele clădiri). Semnalul este de asemenea ciudat - sunt raze transmise orizontal (paralel cu solul, pe care il considerăm o linie dreaptă) și sunt emise din intreaga structură a turnului (de la vârf spre bază). Ne putem imagina că turnul emite o bandă continuă de semnale cu lățimea egală cu înălțimea turnului. Când o rază atinge o clădire, se oprește. *Fiecare clădire primește semnalul utilizând un receptor localizat pe acoperiș*. O clădire primește un mesaj dacă cel puțin o rază ajunge la receptorul ei.
Cu alte cuvinte, o clădire cu numărul de ordine _i_ o sa primească mesajele de la turn doar când: clădirea _i_ este situată la vestul turnului; _i_ nu este mai înaltă decât turnul și nu există o altă clădire _j_ intre ele ([_j_] > _i_) care să fie mai mare decât cladirea _i_.
!problema/towers?tower.png!
În exemplu putem observa că mesajele sunt primite de clădirile [$2$], [$5$], $6$ și [$9$].
Se va construi un singur turn. Guvernul ia în considerare [_K_] variante pentru construirea turnului. Pentru fiecare variantă se cunsoaște înalțimea turnului. Cele [_K_] variante sunt numerotate de la $1$ la [_K_]. Fiecare variantă a turnului are înălțimea diferită de înălțimile celorlalte clădirilor din oraș.
Guvernul dorește să știe care este numărul maxim de clădiri care ar putea să primească mesajele pentru fiecare din cele _K_ variante inainte de a decide ce variată să aleagă. Aceste calcule ar trebui facute pentru fiecare ofertă ținând cont de amplasamentul optim al turnului.
Să se scrie un program care să afișeze numărul maxim de clădiri care ar putea să primească mesaje pentru fiecare variantă. Ca date de intrare o să aveți înalțimile cladirilor și înalțimile turnurilor pentru fiecare variantă. Trebuie să vă gandiți care este locul optim pentru construirea fiecărui turn.
h2. Date de intrare
Fișierul de intrare $towers.in$ ...
Fișierul de intrare $towers.in$ conține pe primul rând două numere întregi pozitive, [_N_] și [_K_]: [_N_] reprezintă numărul clădirilor din oraș și _K_ reprezină numărul variantelor pentru construirea turnului. Al doilea rând conține _N_ numere întregi pozitive reprezentând înălțimile clădirilor din oraș ordonate în funcție de numărul clădirii (de la $1$ la [_N_]). Al treilea rând conține _K_ întregi pozitivi reprezentând înălțimile turnurilor.
h2. Date de ieșire
În fișierul de ieșire $towers.out$ ...
În fișierul de ieșire $towers.out$ se afișează pe un singur rând și separate prin spații, _K_ numere întregi reprezentând numărul maxim de clădiri care ar putea să primească meajele dacă amplasamentul turnului este optim.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ _N_ ≤ 1 000 000$
* $1 ≤ _K_ ≤ 100 000$
* $1 ≤$ înalțimea fiecarei clădiri și înalțimea turnului $≤ 10[^9^]$
* În $20%$ din teste $_N_ ≤ 1 000$ și $_K_ ≤ 20$
* În $30%$ din teste $_N_ ≤ 1 000 000$ și $_K_ ≤ 20$
h2. Exemplu
table(example).
|_. towers.in |_. towers.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 16 3
200 170 155 90 150 140 40 30 185 160 50 110 80 15 70 35
165 180 120
| 5 6 4 |
h3. Explicație
...
!problema/towers?towers4.png!
Clădirile care primesc mesaje sunt: [$10$], [$12$], [$13$], $15$ și [$16$].
!problema/towers?towers2.png!
Clădirile care primesc mesaje sunt: [$2$], [$3$], [$5$], [$6$], $7$ și [$8$].
!problema/towers?towers3.png!
Clădirile care primesc mesaje sunt: [$12$], [$13$], $15$ și [$16$].
== include(page="template/taskfooter" task_id="towers") ==
