Fişierul intrare/ieşire:	unique.in, unique.out	Sursă	ONI 2009 - baraj
Autor	Andrei Grigorean, Paul-Dan Baltescu	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Unique

Miruna şi Laura se joacă cu prietena lor cea mai bună, Omida. Miruna are un şir de N numere naturale şi vrea să găsească o subsecvenţă S de lungime maximă care să respecte următoarea proprietate:
Să conţină cel puţin o dată fiecare număr între 1 şi MaxS, unde MaxS reprezintă valoarea maximă din subsecvenţa S.
Ajutaţi-le pe Laura şi Omida să îi răspundă Mirunei.

Date de intrare

Fişierul de intrare unique.in va conţine:

• pe prima linie un singur număr natural T, reprezentând numărul de teste din fişier.
• Pe linia 2i, (i=1,2,...,T) un număr natural reprezentând numărul de elemente dintr-un şir
• Pe linia 2i+1, (i=1,2,...,T) elementele şirului a cărui lungime este dată pe linia anterioară

Date de ieşire

Fişierul de ieşire unique.out va conţine T linii; pe linia i se va scrie lungimea maximă a unei subsecvenţe a şirului care respectă cerinţa impusă, dat prin liniile 2i şi 2i+1 în fişierul de intrare (i=1,2,...,T).

Restricţii

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100000
• Elementele şirurilor vor fi cuprinse între 1 şi N.

Exemplu

Explicaţie

Cea mai lungă subsecvenţă care respectă condiţia impusă începe pe poziţia 10 şi se termină pe poziţia 15.

Cum se trimit solutii?