B. Добавление на отрезке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть массив $$$a$$$, который изначально состоит из $$$n$$$ нулей. Над этим массивом требуется проделать следующее действие ровно $$$n$$$ раз:

  • выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) и присвоить $$$a_{i} = a_{i} + 1$$$ для каждого $$$i$$$, такого что $$$l \le i \le r$$$.

Вам задается массив $$$b$$$, состоящий из $$$n$$$ целых чисел. Ваша задача — выбрать такие $$$l$$$ и $$$r$$$ для каждого действия, чтобы выполнялось следующее:

  • после того, как все $$$n$$$ действий проделаны, можно переставить элементы местами так, чтобы $$$a$$$ стал равен $$$b$$$;
  • максимальное значение $$$r - l + 1$$$ по всем действиям как можно больше.

Какое максимальное значение $$$r - l + 1$$$ можно получить?

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_{i}$$$ ($$$0 \le b_{i} \le n$$$) — элементы массива $$$b$$$.

Дополнительные ограничения на входные данные:

  • существует хотя бы один способ выбрать $$$l$$$ и $$$r$$$ для каждого действия и переставить элементы местами так, чтобы $$$a$$$ стал равен $$$b$$$;
  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите одно целое число — ответ на задачу.

Пример
Входные данные
3
5
0 5 1 0 1
3
3 2 1
5
1 1 1 1 1
Выходные данные
3
3
1
Примечание

Рассмотрим первый тестовый случай. Если $$$n$$$ действий были следующими:

  • $$$l = 3$$$ и $$$r = 3$$$
  • $$$l = 1$$$ и $$$r = 3$$$
  • $$$l = 3$$$ и $$$r = 3$$$
  • $$$l = 3$$$ и $$$r = 3$$$
  • $$$l = 3$$$ и $$$r = 3$$$

Массив $$$a = [1, 1, 5, 0, 0]$$$, а значит, можно переставить его элементы так, чтобы стало $$$[0, 5, 1, 0, 1]$$$. Как можно видеть, в таком варианте максимальное значение $$$r - l + 1$$$ равно $$$3$$$. Можно показать, что это оптимальный ответ.

Во втором тестовом случае:

  • $$$l = 1$$$ и $$$r = 3$$$
  • $$$l = 2$$$ и $$$r = 3$$$
  • $$$l = 3$$$ и $$$r = 3$$$

Ответ равен $$$3$$$.