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
| Entrada | Saída |
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$$;