== include(page="template/taskheader" task_id="lautari") ==
Bossanip şi Dicsi urmează să se ducă la una dintre cele mai tari petreceri din regat. Bossanip ţine foarte tare la prietenul său, Dicsi, aşa că plănuieşte să îi facă o surpriză în seara petrecerii. Acesta ştie că în faţa clubului unde urmează să se ţină petrecerea vor fi prezenţi lăutarii săi preferaţi şi se decide să le plătească acestora o sumă considerabilă (Bossanip nu se uită niciodată la bani) pentru a îi face o dedicaţie prietenului său.
Cunoscându-i pe lăutari de foarte mult timp, Bossanip ştie că aceştia au o lista de N melodii pe care vor să le cânte, în ordinea data, în seara petrecerii. De asemenea, acesta ştie exact şi ce dedicaţii îi plac lui Dicsi: să nu fie nici prea scurte (strict mai puţin decât P melodii), dar nici prea lungi (strict mai mult decât Q melodii).
Fiindcă vorbim despre o lume cu standarde culturale evoluate, fiecărei melodii dintre cele N îi corespunde un indice de valoare. Astfel, melodiei cu indicele k îi va corespunde valoarea valoare[k]. Mai mult, unei subsecvenţe [i, j] de melodii îi va corespunde o valoare medie egală cu (valoare[i] + valoare[i + 1] + … + valoare[j]) / (j – i + 1), adică media aritmetică a valorilor din subsecventa respectivă.
Luând în considerare toate aceste informaţii, Bossanip vrea să îi dedice prietenului sau o subsecvenţă de melodii care să aibă o valoare medie cât mai mare (nu uitaţi, subsecventa trebuie să fie pe placul lui Dicsi!). Pentru asta el vine la voi şi vă întreabă: care este cea mai mare valoare medie a unei astfel de subsecvenţe?
Bossanip şi Dicsi urmează să se ducă la una dintre cele mai tari petreceri din regat. Bossanip ţine foarte tare la prietenul său, Dicsi, aşa că plănuieşte să îi facă o surpriză în seara petrecerii. Acesta ştie că în faţa clubului unde urmează să se ţină petrecerea vor fi prezenţi lăutarii săi preferaţi şi se decide să le plătească acestora o 'sumă':https://upload.wikimedia.org/wikipedia/commons/9/9b/50_lei._Romania%2C_2005_a.jpg considerabilă (Bossanip nu se uită niciodată la bani) pentru a îi face o dedicaţie prietenului său.
Fiindcă vorbim despre o lume cu standarde culturale evoluate, fiecare lăutar va veni la petrecere cu propriul său instrument muzical (reprezentat printr-un număr natural pozitiv). De asemenea, este posibil ca doi sau mai mulţi lăutari să folosească acelaşi tip de instrument.
Cunoscându-i pe lăutari de foarte mult timp, Bossanip ştie ordinea în care aceştia vor sosi în seara petrecerii. De asemenea, acesta ştie exact şi ce dedicaţii îi plac lui Dicsi: să nu fie nici prea simple, dar nici prea complexe. Astfel, o dedicaţie trebuie să folosească minim $P$ şi maxim $Q$ tipuri de instrumente muzicale diferite. Pe Dicsi nu îl interesează dacă unele instrumente vor fi folosite de mai multe ori pe parcursul unei dedicaţîi. În acelaşi timp, în cadrul unei dedicaţii, lăutarii din cadrul acesteia trebuie să formeze un *interval compact*.
Formal, dacă în cadrul unei dedicaţii vor fi aleşi lăutarii cu numărul de ordine $i$ şi $j$ cu $j > i$, atunci vor trebui să fie aleşi şi toţi lăutarii cu indice de ordine $k$, unde $i < k < j$.
Luând în considerare toate aceste informaţii, Bossanip vrea să îi aleagă prietenului său o subsecvenţă de lăutari care să respecte cerinţele date (nu uitaţi, subsecvenţa trebuie să fie pe placul lui Dicsi!). Pentru asta el vine la voi şi vă întreabă: câte modalităţi are de a alege trupa de lăutari?
Două modalităţi se consideră distincte dacă şi numai dacă mulţimea de lăutari care sunt aleşi (mulţimea de poziţii) este diferită.
h2. Date de intrare
Fişierul de intrare $lautari.in$ conţine pe prima linie 3 numere naturale N, P, Q. Următoarele N linii conţin valorile melodiilor cântate de lăutari, pe linia i+1 a fişierului aflându-se valoarea melodiei cu indicele i.
Fişierul de intrare $lautari.in$ conţine pe prima linie 3 numere naturale $N$, $P$, $Q$. Cea de-a doua linie va conţine tipurile instrumentelor muzicale folosite de lăutari, în ordinea în care aceştia ajung la petrecere (fiecărui instrument muzical îi este atribuit un număr natural, iar două instrumente sunt de acelaşi tip dacă le sunt atribuite numere egale), separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $lautari.out$ va conţine o singură valoare, şi anume valoarea medie a unei subsecvenţe valide.
În fişierul de ieşire $lautari.out$ se va afla o singură valoare, şi anume numărul total de secvenţe valide.
h2. Restricţii
* $1 ≤ N ≤ 100000$
* $1 ≤ N ≤ 100.000$
* $1 ≤ P ≤ Q ≤ N$
* $1 ≤ valoare[i] ≤ 100000, oricare ar fi 1 ≤ i ≤ N$
* $Răspunsul se va considera valid dacă diferă cu maxim 0.01 de răspunsul corect.$
* $Valorile instrumentelor muzicale au valori naturale nenule mai mici sau egale ca 100.000$
* $Pentru teste in valoare de 10 de puncte N ≤ 200$
* $Pentru teste in valoare de 30 de puncte N ≤ 5.000$
h2. Exemplu
table(example). |_. lautari.in |_. lautari.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 2 3
1 3 3 2 3
| 9
|
| 3 1 1
1 1 1
| 6
|
h3. Explicaţie
...
Subsecvenţele valide pentru primul exemplu sunt:
$1 3$
$1 3 3$
$1 3 3 2$
$1 3 3 2 3$
$3 3 2$
$3 3 2 3$
$3 2$
$3 2 3$
$2 3$
== include(page="template/taskfooter" task_id="lautari") ==
