== include(page="template/taskheader" task_id="towers") ==
Orasul X este compus din $N$ blocuri, ordonate sub forma unei secvente numerotate de la $1$ la $N$, de la vest la est. *Fiecare bloc are o inaltime diferita - un numar intreg, respectiv $h{~1~}, h{~2~}, ..., h{~N~}$*. Guvernul planuieste sa construiasca un turn, stiuat in aceeasi secventa cu blocurile (poate sa fie inaltimea primului bloc, intre oricare doua blocuri sau dupa ultimul bloc). Turnul osa transmita mesaje cetatenilor. *Turnul trebuie sa aiba inaltimea $H$, care trebuie sa fie diferita de toate celelalte inaltimi ale blocurilor.
Orasul X este compus din $N$ blocuri, ordonate sub forma unei secvente numerotate de la $1$ la $N$, de la vest la est. *Fiecare bloc are o inaltime diferita - un numar intreg, respectiv $h{~1~}, h{~2~}, ..., h{~N~}$*. Guvernul planuieste sa construiasca un turn, stiuat in aceeasi secventa cu blocurile (poate sa fie inaintea primului bloc, intre oricare doua blocuri sau dupa ultimul bloc). Turnul o sa transmita mesaje cetatenilor. *Turnul trebuie sa aiba inaltimea $H$, care trebuie sa fie diferita de toate celelalte inaltimi ale blocurilor*.
Din cauza unor idei ingineresti destul de ciudate, turnul va putea transmite semnale doar in vest (spre inceputul secventei de blocuri). Semnalele sunt de asemenea ciudate - acestea sunt unde care traverseaza orizontal (parelele cu solul, pe care le consideram linii drepte) si sunt emise din toata suprafata blocului (de sus in jos). Deci, ne putem imagina ca turnul emite o banda continua de semnale cu latimea egala cu inaltimea turnului. Cand o unda intalneste un bloc, se opreste. *Fiecare bloc primeste semnalele semnalele folosind un receptor localizat in varful acestuia. Un bloc primeste un mesaj daca cel putin o unda atinge receptorul.
Din cauza unor idei ingineresti destul de ciudate, turnul va putea transmite semnale doar catre vest (spre inceputul secventei de blocuri). Semnalele sunt de asemenea ciudate - acestea sunt unde care traverseaza orizontal (parelele cu solul, pe care le consideram linii drepte) si sunt emise din toata suprafata blocului (de sus in jos). Deci, ne putem imagina ca turnul emite o banda continua de semnale cu latimea egala cu inaltimea turnului. Cand o unda intalneste un bloc, se opreste. *Fiecare bloc primeste semnalele semnalele folosind un receptor localizat in varful acestuia. Un bloc primeste un mesaj daca cel putin o unda atinge receptorul*.
Cu alte cuvinte, blocul cu indicele $i$ va primi mesaje de la turn doar atunci cand: blocul $i$ este situat in stanga turnului; $i$ nu este mai inalt decat turnul si nu exista un alt bloc $j$ intre ele ($j$ > $i$), care este mai inalt decat blocul $i$.
Cu alte cuvinte, blocul cu indicele $i$ va primi mesaje de la turn doar atunci cand: blocul $i$ este situat in stanga turnului; $i$ nu este mai inalt decat turnul si nu exista un alt bloc $j$ intre ele ({$j$} > {$i$}), care este mai inalt decat blocul $i$.
(Poza)
!>problema/towers?img.png!
Uitati-va la exemplul din figura de mai sus: blocurile care receptioneaza mesaje sunt cele cu indicii $2$, $5$, $6$, $9$.
Uitati-va la exemplul din figura alaturata: blocurile care receptioneaza mesaje sunt cele cu indicii $2$, $5$, $6$, $9$.
Un singur turn o sa fie construit, cu taote acestea guvernul a primit oferte pentru $K$ variante de turnuri, fiecare avend o inaltime diferita. Ofertele de turnuri usnt numerotate de la $1$ la $K$. Fiecare turn are inaltimea sa, care este de asemenea diferita de inaltimea blocurilor. Liderii orasului doresc sa afle numarul maxim de blocuri, care ar primi mesajele, pentru fiecare dintre cele $K$ oferte de turnuri, inainte de a lua decizia oficiala. Desigur, raspunsurile trebuie determinate considerand asezarea optima a fiecarui turn.
Un singur turn o sa fie construit, cu toate acestea guvernul a primit oferte pentru $K$ variante de turnuri, fiecare avend o inaltime diferita. Ofertele de turnuri sunt numerotate de la $1$ la $K$. Fiecare turn are inaltimea sa, care este de asemenea diferita de inaltimea blocurilor. Liderii orasului doresc sa afle numarul maxim de blocuri, care ar primi mesajele, pentru fiecare dintre cele $K$ oferte de turnuri, inainte de a lua decizia oficiala. Desigur, raspunsurile trebuie determinate considerand asezarea optima a fiecarui turn.
Scrieti un program *towers* care sa determine numarul maxim de blocuri care ar primi mesaje pentru fiecare din cele $K$ oferte. Se da secventa de blocuri din oras (mai exact, inaltimile lor) si inaltimile tuturor ofertelor de turnuri.
Sa se determine numarul maxim de blocuri care ar primi mesaje pentru fiecare din cele $K$ oferte, date fiind secventa de blocuri din oras (mai exact, inaltimile lor) si inaltimile tuturor ofertelor de turnuri.
h2. Date de intrare
* $1 ≤ N ≤ 1 000 000$
* $1 ≤ K ≤ 1 000 000$
* $1 ≤ inaltimea fiecarui bloc si oferte de turnuri ≤ 10^9 $
* $1 ≤ inaltimea fiecarui bloc si oferte de turnuri ≤ 10^9^$
* Pentru $20$% din teste $N ≤ 1000$, $K ≤ 20$
* Pentru alte $30$% din teste $N ≤ 1 000 000$, $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
h3. Nota
...
A se observa ca in imaginea de mai sus inaltimile turnurilor $3$ si $5$ sunt inversate, fapt semnalat de catre comisie in timpul concursului.
== include(page="template/taskfooter" task_id="towers") ==
