Собеседование в Сбер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После выпуска из Университета МИСИС Ваня решил устроиться программистом в Сбер. Чтобы успешно пройти собеседование, он решил полностью прорешать архив задач. К сожалению, архив оказался старым, и в нём нельзя было отсортировать задачи по сложности. Сложность каждой задачи обозначена целым числом.

Ваня придумал следующую стратегию: каждый день он будет просматривать задачи одну за другой, с первой до последней. Если текущую задачу он ещё не решал и уровень его навыка достаточен для её решения, то он решает её, и его навык увеличивается на $$$1$$$. Ваня может решить задачу, если его навык больше или равен сложности задачи.

Изначально уровень навыка Вани равен $$$1$$$. Сколько дней потребуется Ване, чтобы быть готовым к собеседованию?

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество задач в архиве.

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

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

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

Если Ваня сможет решить все задачи из архива, выведите, какое количество дней ему понадобится. В ином случае выведите $$$-1$$$.

Пример

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

    441 2 4 333 1 152 4 3 2 511

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

    2
    2
    -1
    1