Codeforces Round 983 (Div. 2) |
---|
Finished |
You are given an array $$$a$$$ of $$$n$$$ elements $$$a_1, a_2, \ldots, a_n$$$.
You can perform the following operation any number (possibly $$$0$$$) of times:
Find the minimum number of operations required to make the array $$$a$$$ satisfy the condition:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the minimum number of operations required.
471 2 3 4 5 6 731 3 234 5 3159 3 8 1 6 5 3 8 2 1 4 2 9 4 7
3 1 0 8
In the first test case, one of the possible series of operations would be:
It can be proven that any triplet of elements with pairwise distinct indices in the final array forms a non-degenerate triangle, and there is no possible answer using less than $$$3$$$ operations.
In the second test case, we can assign $$$a_1 := a_2 = 3$$$ to make the array $$$a = [3, 3, 2]$$$.
In the third test case, since $$$3$$$, $$$4$$$ and $$$5$$$ are valid side lengths of a triangle, we don't need to perform any operation to the array.
Name |
---|