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

==Include(page="template/taskheader" task_id="panouri")==
 
Pe autostrada "Soarele Estului " sunt asezate de-a lungul soselei, la distante egale, panouri publicitare ale unor firme. Aceeasi firma, poate sa aiba mai multe panouri publicitare si fiecare panou poate sa apara in mai multe locuri. Tipurile de panouri se identifica prin numere naturale, numarul total de panouri fiind $N$.
Firma "X Corporation" are panouri de $T$ tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic in apropierea autostrazii; de aceea, pentru alegerea locului, este interesata si de urmatorul aspect: care este lungimea minima de sosea, in care se pot intalni, toate cele $T$ tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, si indiferent daca intre ele se mai interpun sau nu panouri ale altor firme.
 
h2. Cerinta
 
Cunoscand $N$ - numarul total de panouri de la marginea autostrazii si ordinea amplasarii lor, ca si cele $T$ tipuri de panouri amplasate de firma, determinati numarul minim de intervale dintre doua panouri intre care firma "X Corporation" isi regaseste toate panourile sale.
 
h2. Date de Intrare
 
Fisierul de intrare $panouri.in$ are pe prima linie numerele $N$ si $T$. Pe urmatoarele $N$ linii, sunt $N$ numere naturale, nu neaparat diferite, cate unul pe linie, fiecare numar reprezentind tipul panoului respectiv, iar incepand cu linia $N + 2$, cate unul pe linie, cele $T$ tipuri de panouri diferite al firmei.
 
h2. Date de Iesire
 
Fisierul de iesire $panouri.out$ va contine pe prima linie un singur numar intreg pozitiv $L$, reprezentand numarul cerut, sau $-1$ in caz ca nu exista solutie.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 200.000$
* $1 ≤ T ≤ 20.000$
* Toate numerele reprezentand panouri sunt numere naturale din intervalul $[1..20.000]$
 
h2. Exemple
 
table(example). |_. panouri.in |_. panouri.out |
| 6 2
  1
  2
  3
  5
  3
  1
  5
  1
| 2 |
| 8 3
  5
  1
  3
  3
  5
  4
  2
  1
  3
  1
  4
| 4 |
 
h3. Explicatii
 
* Sunt N = 6 panouri : 1 2 3 5 3 1. Firma are T = 2 tipuri de panouri: 5 si 1. Cea mai scurta secventa care contine elementele 5 si 1, este intre panourile  al 4 – lea si al 6 -lea , si contine 2 intervale.
* Sunt N = 8 panouri de tipurile: 5 1 3 3 5 4 2 1. Firma are T = 3 tipuri de panouri: 3, 1 si 4. Cea mai scurta secventa care contine elementele 1, 3 si 4, este intre al 2 lea si al 6-lea panou, si contine 4 intervale.
 
 
==Include(page="template/taskfooter" task_id="panouri")==
 
 

==Include(page="template/raw")==
 
Link: [1]File-List
 
panouri
 
 
 
Pe autostrada "Soarele Estului " sunt asezate de-a lungul soselei, la distante egale, panouri publicitare ale unor firme. Aceeasi firma, poate sa aiba mai multe panouri publicitare si fiecare panou poate sa apara in mai multe locuri. Tipurile de panouri se identifica prin numere naturale, numarul total de panouri fiind N.
 
 
 
Firma "X Corporation" are panouri de T tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic in apropierea autostrazii; de aceea, pentru alegerea locului, este interesata si de urmatorul aspect: care este lungimea minima de sosea, in care se pot intalni, toate cele T tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, si indiferent daca intre ele se mai interpun sau nu panouri ale altor firme.
 
h2. Cerinta
 
Cunoscand N - numarul total de panouri de la marginea autostrazii si ordinea amplasarii lor, ca si cele T tipuri de panouri amplasate de firma, determinati numarul minim de intervale dintre doua panouri intre care firma "X Corporation" isi regaseste toate panourile sale.
 
h2. Date de Intrare
 
Fisierul de intrare panouri.in are pe prima linie numerele N si T. Pe urmatoarele N linii, sunt N numere naturale, nu neaparat diferite, cate unul pe linie, fiecare numar reprezentind tipul panoului respectiv, iar incepand cu linia N + 2, cate unul pe linie, cele T tipuri de panouri diferite al firmei.
 
h2. Date de Iesire
 
Fisierul de iesire panouri.out va contine pe prima linie un singur numar intreg pozitiv L, reprezentand numarul cerut, sau -1 in caz ca nu exista solutie.
 
h2. Restrictii si precizari
 
. 1 <= N <= 200.000
 
. 1 <= T <= 20.000
 
. Toate numerele reprezentand panouri sunt numere naturale din intervalul [1..20.000].
 
 
 
Exemple
 
panouri.in panouri.out Explicatii
6 2 2 Sunt N = 6 panouri : 1 2 3 5 3 1. Firma are T = 2 tipuri de panouri: 5 si 1.
 
1
 
2 Cel mai scurta secventa care contine elementele 5 si 1, este intre panourile al 4 - lea si al 6 -lea , si contine 2 intervale.
 
3
 
5
 
3
 
1
 
5
 
1
8 3 4 Sunt N = 8 panouri de tipurile: 5 1 3 3 5 4 2 1. Firma are T = 3 tipuri de panouri: 3, 1 si 4.
 
5
 
1 Cel mai scurta secventa care contine elementele 1, 3 si 4, este intre al 2 lea si al 6-lea panou, si contine 4 intervale.
 
3
 
3
 
5
 
4
 
2
 
1
 
3
 
1
 
4
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/panouri/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="panouri")==

1090