Fișierul intrare/ieșire	towers.in, towers.out	Sursă	Shumen 2016 Seniori
Autor		Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	3 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

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

Vezi soluțiile trimise | Statistici

Towers

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₁, h₂, .., 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.

Î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.

Date de intrare

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.

Date de ieșire

Î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.

Restricții

• 1 ≤ N ≤ 1 000 000
• 1 ≤ K ≤ 100 000
• 1 ≤ înalțimea fiecarei clădiri și înalțimea turnului ≤ 10⁹
• În 20% din teste N ≤ 1 000 și K ≤ 20
• În 30% din teste N ≤ 1 000 000 și K ≤ 20

Exemplu

Explicație

Clădirile care primesc mesaje sunt: 10, 12, 13, 15 și 16.

Clădirile care primesc mesaje sunt: 2, 3, 5, 6, 7 și 8.

Clădirile care primesc mesaje sunt: 12, 13, 15 și 16.