В один день BThero решил поиграться с массивами и придумал следующую задачу:
Вам дан массив \(a\), состоящий из \(n\) положительных целых чисел. Массив нумеруется с \(1\) до \(n\). Вы выполняете следующую процедуру ровно один раз:
Найдите и выведите минимальное возможное значение \(|b|\) (размер массива \(b\)), которое вы можете получить в конце процедуры. Можно показать, что с заданными ограничениями всегда есть хотя бы один способ построить массив \(b\).
В первой строке входного файла задано одно целое число \(T\) (\(1 \le T \le 5 \cdot 10^5\)) — кол-во наборов входных данных. Далее следуют \(T\) наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 5 \cdot 10^5\)).
Вторая строка содержит \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) (\(2 \le a_i \le 10^9\)).
Гарантируется, что \(\sum{n}\) по всем наборам входных данных не превосходит \(5 \cdot 10^5\).
Для каждого набора входных данных выведите в новой строке одно положительное целое число — минимальное возможное значение \(|b|\).
3 3 6 8 2 1 4 3 5 6 6
3 1 2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач