C. Паприка и перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Паприка любит перестановки. У неё есть массив $$$a_1, a_2, \dots, a_n$$$. Она хочет сделать массив перестановкой целых чисел от $$$1$$$ до $$$n$$$.

Чтобы достичь этой цели, она может применять к массиву операции. За одну операцию она может выбрать два целых числа $$$i$$$ ($$$1 \le i \le n$$$) и $$$x$$$ ($$$x > 0$$$), и затем присвоить $$$a_i := a_i \bmod x$$$ (то есть заменить $$$a_i$$$ на остаток от деления $$$a_i$$$ на $$$x$$$). В разных операциях выбираемые $$$i$$$ и $$$x$$$ могут быть разными.

Определите минимальное количество операций, необходимое, чтобы сделать массив перестановкой целых чисел от $$$1$$$ до $$$n$$$. Если это невозможно, выведите $$$-1$$$.

Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество операций, необходимое, чтобы сделать массив перестановкой целых чисел от $$$1$$$ до $$$n$$$, или $$$-1$$$, если это невозможно.

Пример
Входные данные
4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7
Выходные данные
1
-1
4
2
Примечание

В первом наборе входных данных единственная возможная последовательность операций, минимизирующая количество операций, следующая:

  • Выберем $$$i=2$$$, $$$x=5$$$. Заменим $$$a_2 := a_2 \bmod 5 = 2$$$.

Для второго набора входных данных невозможно получить перестановку целых чисел от $$$1$$$ to $$$n$$$.