#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/C

Repovive

All Triangles - Repovive Standard Round 1 (Sponsored by TIG Foundation) | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

4C. All Triangles

1500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Consider a sequence $a_1, a_2, \ldots, a_m$ of positive integers. We call this sequence nice if for every choice of three distinct indices $i,j,k$ , the lengths $a_i, a_j, a_k$ can be the side lengths of a (non-degenerate) triangle.

You are given an array $a_1, a_2, \ldots, a_n$ . Remove the minimum number of elements so that the remaining sequence becomes nice.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

5
3
3 4 5

Case 1

4
1 3 4 5

Case 2

6
1 1 1 10 10 10

Case 3

2
1 1000

Case 4

4
5 5 5 5

Explanation

Case 1

Scenario 1: $n=3$ , $a=[3, 4, 5]$ . Sorted: $[3, 4, 5]$ . The only triple is $(3, 4, 5)$ : $3+4=7 > 5$ , $3+5=8 > 4$ , $4+5=9 > 3$ . The array is already nice. No elements need to be removed.

Case 2

Scenario 2: $n=4$ , $a=[1, 3, 4, 5]$ . Sorted: $[1, 3, 4, 5]$ . The triple $(1, 3, 5)$ fails: $1+3=4 \not> 5$ . The longest nice subsequence is $[3, 4, 5]$ (length $3$ ): $3+4=7 > 5$ . Remove $1$ element. Answer: $4 - 3 = 1$ .

Case 3

Scenario 3: $n=6$ , $a=[1, 1, 1, 10, 10, 10]$ . Sorted: $[1, 1, 1, 10, 10, 10]$ . The subset $[1, 10, 10, 10]$ is nice: every triple is of the form $(1, 10, 10)$ or $(10, 10, 10)$ , and $1+10=11 > 10$ holds. This gives a nice subsequence of length $4$ . No nice subsequence of length $5$ or $6$ exists (any two $1$ s paired with a $10$ gives $1+1=2 \not> 10$ ). Answer: $6 - 4 = 2$ .

Case 4

Scenario 4: $n=2$ , $a=[1, 1000]$ . With only $2$ elements, no triple of elements exists, so the array is trivially nice. Answer: $0$ .

Case 5

Scenario 5: $n=4$ , $a=[5, 5, 5, 5]$ . All elements are equal. Every triple $(5, 5, 5)$ satisfies $5+5=10 > 5$ . The array is already nice. Answer: $0$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given an array $a_1, a_2, \ldots, a_n$ . Remove the minimum number of elements so that the remaining sequence becomes nice.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Scenario 1: $n=3$ , $a=[3, 4, 5]$ . Sorted: $[3, 4, 5]$ . The only triple is $(3, 4, 5)$ : $3+4=7 > 5$ , $3+5=8 > 4$ , $4+5=9 > 3$ . The array is already nice. No elements need to be removed.

Scenario 4: $n=2$ , $a=[1, 1000]$ . With only $2$ elements, no triple of elements exists, so the array is trivially nice. Answer: $0$ .

Scenario 5: $n=4$ , $a=[5, 5, 5, 5]$ . All elements are equal. Every triple $(5, 5, 5)$ satisfies $5+5=10 > 5$ . The array is already nice. Answer: $0$ .