Fișierul intrare/ieșire secvdom.in, secvdom.out Sursă codeforces.com
Autor autor necunoscut Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.9 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Secvență Dominată

Se dă un vector V cu N numere naturale. O secvență a vectorului V este o parte continuă a acestuia, încadrată între doi indici i și j, cu 1 ≤ ijN. Notăm cu freq(x) numărul de apariții ale lui x într-o secvență. Spunem că o secvență este dominată de o valoare x dacă:

  • Secvența are lungime ≥ 2.
  • Pentru orice alt număr y din secvență, freq(y) < freq(x).

De exemplu:

  • [1, 2, 3, 4, 5, 2] este dominată de 2
  • [11, 11] este dominată de 11
  • [3, 2, 3, 2, 2] este dominată de 2
  • [1, 2, 1, 2] nu este dominată
  • [3, 3, 2, 2, 1] nu este dominată
  • [ 1] nu este dominată

Atenție!

O secvență nu poate fi dominată de două valori.

Cerință

Dându-se vectorul V de N numere naturale, să se calculeze lungimea celei mai mici subsecvențe care este dominată de o valoare.

Date de intrare

Fișierul de intrare secvdom.in conține pe prima linie T, reprezentând numărul de teste. Fiecare din cele T teste va fi reprezentat prin două linii: pe prima linie se va afla numărul N, iar pe cea de-a doua linie se vor găsi N numere naturale (vectorul V).

Date de ieșire

În fișierul de ieșire secvdom.out se vor găsi T linii, pe linia i a acestuia aflându-se răspunsul la cel de-al i-lea test.

Restricții

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 200.000
  • 1 ≤ V[i] ≤ 1.000.000

Exemplu

secvdom.in secvdom.out Explicații
4
1
1
6
1 2 3 4 5 1
9
4 1 2 4 5 4 3 2 1
4
3 3 3 3
-1
6
3
2
Avem patru teste.
 
Primul test constă dintr-o secvență de 1 număr: [1]. Ea nu conține nici o subsecvență
dominată, deci răspundem -1.
 
Al doilea test constă din secvența [1 2 3 4 5 1] a cărei cea mai mică subsecvență
dominată este ea însăși, de lungime 6, deci răspundem 6.
 
Al treilea test constă din secvența [4 1 2 4 5 4 3 2 1]. Cea mai mică subsecvență
dominată este [4 5 4], de lungime 3, deci răspundem 3.
 
Al patrulea test constă din secvența [3 3 3 3]. Cea mai mică subsecvență dominată
este [3 3], deoarece o secvență dominată are lungime minim doi. Raspundem 2.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii