Напомним, что перестановка длины $$$n$$$ — это последовательность из $$$n$$$ целых чисел, в которой каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.
Определим стоимость перестановки как минимальную длину ее непрерывного подотрезка (возможно, пустого), который необходимо отсортировать, чтобы вся перестановка стала отсортированной в порядке возрастания.
Вам дан массив целых чисел $$$p$$$, состоящий из целых чисел от $$$0$$$ до $$$n$$$, где ни одно положительное целое число не повторяется. Вам нужно заменить нули на целые числа так, чтобы массив $$$p$$$ стал перестановкой.
Ваша задача — вычислить максимальную возможную стоимость получившейся перестановки.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n$$$). Ни одно положительное целое число не встречается два или более раза в этой последовательности.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальная возможная стоимость получившейся перестановки.
451 0 4 0 530 0 041 2 3 030 3 2
3302
В первом примере вы можете сделать перестановку $$$[1, 3, 4, 2, 5]$$$ со стоимостью $$$3$$$, потому что вам нужно отсортировать отрезок $$$[2, 4]$$$.
Во втором примере вы можете сделать перестановку $$$[2, 3, 1]$$$ со стоимостью $$$3$$$, потому что вам нужно отсортировать отрезок $$$[1, 3]$$$.
В третьем примере существует только одна возможная перестановка — $$$[1, 2, 3, 4]$$$, со стоимостью $$$0$$$, потому что перестановка уже отсортирована.
В четвертом примере существует только одна возможная перестановка — $$$[1, 3, 2]$$$, со стоимостью $$$2$$$, потому что вам нужно отсортировать отрезок $$$[2, 3]$$$.
