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 $Max_S$, unde $Max_S$ reprezintă valoarea maximă din subsecvenţa $S$.

Cerință

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 $2 \cdot i$, $(i = 1, 2, \dots, T)$. un număr natural reprezentând numărul de elemente dintr-un şir
• Pe linia $2 \cdot i + 1$, $(i = 1, 2, \dots, 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 $2 \cdot i$ şi $2 \cdot i + 1$ în fişierul de intrare $(i = 1, 2, \dots, T)$.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N \leq 100 \ 000$
• Elementele şirurilor vor fi cuprinse între $1$ şi $N$.

Exemplu

unique.in

1
16
3 1 4 5 2 7 5 2 8 3 1 3 1 2 3 9

unique.out

6

Explicație

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