Fişierul intrare/ieşire:	lautari.in, lautari.out	Sursă	FMI No Stress 8
Autor	Andrei Arnautu, Eugenie Daniel Posdarascu	Adăugată de	Fmi no stress 2018 •fminostress2018
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

Fiindcă vorbim despre o lume cu standarde culturale evoluate, fiecare lăutar va veni la petrecere cu propriul său instrument muzical. 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 că aceştia au o listă de N melodii pe care vor să le cânte, în ordinea dată, î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, melodiile dintr-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.

Luând în considerare toate aceste informaţii, Bossanip vrea să îi dedice prietenului său o subsecvenţă de melodii 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 o dedicaţie validă?

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 tipurile instrumentelor muzicale folosite de lăutari (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), pe linia i+1 a fişierului aflându-se numărul corespunzator instrumentului folosit de lăutarul cu indicele i.

Date de ieşire

În fişierul de ieşire lautari.out se va afla o singură valoare, şi anume numărul total de secvenţe valide.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ P ≤ Q ≤ N
• 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

Exemplu

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

Cum se trimit solutii?