secventa

Secventa

== include(page="template/taskheader" task_id="secventa") ==

==Include(page="template/taskheader" task_id="secventa")==

Poveste ...

Gigel are un sir de $N$ numere intregi. Toata lumea stie ca o secventa este un subsir de numere care apar pe pozitii consecutive in sirul initial. Gigel a definit baza unei secvente ca fiind minimul valorilor elementelor din secventa respectiva.

h2. Cerinta

...
 
h2. Restrictii
 
...

Fiind dat un numar natural $K$, determinati pentru Gigel o secventa de lungime cel putin $K$ cu baza maxima.

h2. Date de intrare

...

Fisierul de intrare $secventa.in$ contine pe prima linie numerele {$N$} si {$K$}, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.

h2. Date de iesire

...

Fisierul de iesire $secventa.out$ trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de lungime cel putin $K$ cu baza maxima si valoarea maxima a bazei.
 
h2. Restrictii si precizari
 
* $1 ≤ K ≤ N ≤ 500 000$
* Elementele din vector sunt numere intregi din intervalul $[-30 000, 30 000]$
* Daca exista mai multe solutii pentru care se obtine baza maxima, atunci se va alege cea in care pozitia de inceput a secventei este cea mai mica, iar in caz de egalitate cea in care pozitia de sfarsit a secventei este cea mai mica

h2. Exemplu

| secventa.in | secventa.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. secventa.in|_. secventa.out|
|8 3
-1 2 3 1 0 4 8 6
|6 8 4|
 
_Explicatie_: Secventa care incepe pe pozitia 6 si se termina pe pozitia 8 (de lungime 3) este ({$4$}, {$8$}, {$6$}) are baza {$minim(4, 8, 6) = 4$}. Nu mai exista o secventa cu lungime mai mare sau egala cu $3$ care sa aiba baza mai mare.

== include(page="template/taskfooter" task_id="secventa") ==
 

==Include(page="template/taskfooter" task_id="secventa")==