A1. Потерянная цивилизация (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вы должны вычислить значение для одной последовательности. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Определим алгоритм для генерации последовательности из $$$m+k$$$ целых чисел следующим образом:

  1. Сначала получите последовательность $$$x$$$ из $$$m$$$ целых чисел в качестве входных данных. Если $$$k=0$$$, немедленно завершите алгоритм и верните последовательность $$$x$$$.
  2. Затем выберите любой индекс $$$1 \le i \le |x|$$$ и вставьте $$$(x_i+1)$$$ сразу после элемента $$$x_i$$$.
  3. Если $$$x$$$ содержит ровно $$$m+k$$$ целых чисел, завершите выполнение и верните последовательность $$$x$$$. В противном случае вернитесь ко второму шагу.

Алиса знает, что этот алгоритм использовался древней цивилизацией для того, чтобы надежно скрыть свои секреты. Алиса хочет узнать знания, которые они хотели скрыть, но это не простая задача — вывести входные данные из выходных данных алгоритма.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$).

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$300\,000$$$.

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

Для каждого набора входных данных выведите длину кратчайшей последовательности на отдельной строке.

Пример
Входные данные
5
5
1 2 3 4 5
5
1 3 5 7 9
5
1 2 5 6 5
7
1 2 4 5 3 7 8
9
9 8 9 2 3 4 4 5 3
Выходные данные
1
5
3
4
3
Примечание

В первом наборе входных данных последовательность $$$[1]$$$ может сгенерировать последовательность $$$a=[1,2,3,4,5]$$$ следующим образом:

$$$$$$[1] \to [1,\color{red}{2}] \to [1,2,\color{red}{3}] \to [1,2,3,\color{red}{4}] \to [1,2,3,4,\color{red}{5}]$$$$$$

Во втором наборе входных данных единственной последовательностью, которая может сгенерировать $$$a=[1,3,5,7,9]$$$, является сама последовательность $$$a$$$.