Bombons do Enzinho

Enzinho está muito feliz, pois comprou $N$ bombons, e os guardou em fila! O bombom $i$ tem um valor de doçura $a_i$. Ele quer dividir eles em $k> 1$ intervalos, e então comer todos de um grupo em cada dia. Ele diz que uma divisão é boa caso o MEX dos valores de doçuras de cada um dos intervalos seja o mesmo. O MEX de uma sequência $x_1, x_2, \cdots , x_n$ é o menor valor $y \ge 0$ tal que $y$ não aparece na sequência. Por exemplo, o MEX de $2, 2, 1$ é 0, pois $0$ não pertence a sequência, o MEX de $3,1, 0, 1$ é 2, já que $0$ e $1$ aparecem na sequência, e $2$ não, e o MEX de $0, 3, 1, 2$ é $4$, pois $0, 1, 2, 3$ aparecem na sequência, mas o $4$ não.

Sua tarefa é ajudar o Enzinho a encontrar alguma divisão boa dos seus bombons!

Entrada

O input consiste de múltiplos casos de teste. A primeira linha contém um inteiro $t$ ($1 \leq t \leq 10^4$) - o número de casos de teste.

A primeira linha de cada caso de teste contém o inteiro $n$ ($1 \leq n \leq 10^5$), a quantidade de bombons. A segunda linha contém $n$ inteiros $a_i$ ($0 \leq a_i < n$), o valor de doçura de cada bombom.

É garantido que a soma de $n$ sobre todos os casos de teste não excede $10^5$.

Saída

Para cada caso de teste imprima $-1$, caso não exista nenhuma divisão. Caso exista, imprima $k \ge 2$, o número de intervalos, e então, imprima $k$ linhas. Em cada linha, imprima 2 valores $l_i, r_i$ ($1 \le l_i \le r_i \le n$), que são os limites do $i$-ésimo intervalo.

As seguintes condições tem que ser satisfeitas:

• Para todo $1 \le j < k, l_{j+1} = r_j + 1$.
• $l_1 = 1, r_k = n$

Se tem múltiplas soluções, imprima alguma delas.

Exemplos

5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
2 2 2
4
0 1 2 0

2
1 1
2 2
-1
3
1 3
4 5
6 8
3
1 1
2 2
3 3
-1

Notas:

No primeiro caso, os $2$ bombons tem valores $0, 0$. Então, essa sequência de bombons pode ser dividas em $2$ intervalos, $[1, 1]$ e $[2, 2]$:

• O MEX do primeiro intervalo $[0]$ é 1, já que $0$ está na sequência e $1$ não está.
• O MEX do segundo intervalo $[0]$ também é 1, já que $0$ está na sequência e $1$ não.

No segundo caso teste, pode ser provado que não existe uma divisão possível.

No terceiro caso teste, a sequência de bombons $[0, 1, 7, 1, 0, 1, 0, 3]$ pode ser dividida em $3$ intervalos, $[1, 3], [4, 5], [6, 8]$.

• O MEX da sequência $[0, 1, 7]$ é $2$;
• O MEX da sequência $[1, 0]$ é $2$;
• O MEX da sequência $[1, 0, 3]$ é $2$;

Para submeter sua solução use esse link