Fișierul intrare/ieșire | secvdom.in, secvdom.out | Sursă | codeforces.com |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.9 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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 ≤ i ≤ j ≤ N. 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. |