CF2170B Addition on a Segment

You start with an integer array $ a $ , which initially consists of $ n $ zeros. You have to perform the following action exactly $ n $ times: - choose two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) and assign $ a_{i} = a_{i} + 1 $ for each $ i $ such that $ l \le i \le r $ . You are given an array $ b $ , consisting of $ n $ integers. Your task is to choose such values $ l $ and $ r $ for each action that: - after all $ n $ actions are performed, it's possible to reorder the elements in such a way that $ a $ becomes equal to $ b $ ; - the maximum value of $ r - l + 1 $ over all actions is as large as possible. What's the maximum possible value of $ r - l + 1 $ ?

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^{5} $ ) — the length of the array $ b $ . The second line of each test case contains $ n $ integers $ b_{i} $ ( $ 0 \le b_{i} \le n $ ) — the elements of the array $ b $ . Additional constraints on the input: - there exists at least one way to choose $ l $ and $ r $ for each action and reorder the elements at the end so that $ a $ becomes equal to $ b $ ; - the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output one integer — the answer to the problem.

Consider the first test case. If the $ n $ actions were as follows: - $ l = 3 $ and $ r = 3 $ - $ l = 1 $ and $ r = 3 $ - $ l = 3 $ and $ r = 3 $ - $ l = 3 $ and $ r = 3 $ - $ l = 3 $ and $ r = 3 $ The array $ a = [1, 1, 5, 0, 0] $ , so you can reorder the elements to make it equal to $ [0, 5, 1, 0, 1] $ . As can be seen in this case, the maximum value of $ r - l + 1 $ is $ 3 $ . It can be shown that this is the optimal answer. In the second test case: - $ l = 1 $ and $ r = 3 $ - $ l = 2 $ and $ r = 3 $ - $ l = 3 $ and $ r = 3 $ The answer is $ 3 $ .