#591 Mochi

Loading problem...

Preparing the statement, recent submissions, and submit form.

#591 Mochi

Time limit: 1000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

You are given $N$ rice cakes. The size of the $i$ -th rice cake is $A_i$ .

You may choose two unused rice cakes and make one bundle. The rice cake placed on top must be strictly larger than the one placed below. A rice cake cannot be used in more than one bundle.

Find the maximum number of bundles that can be made.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

For each test case, print the maximum number of bundles.

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq A_i \leq 10^9$ ( $1 \leq i \leq N$ ).
The sum of $N$ over all test cases does not exceed $200\,000$ .

Subtasks

#	Score	Constraints
1	7	$N \leq 10$ . The sum of $N$ over all test cases does not exceed $2\,000$ .
2	14	$A_1,A_2,\cdots,A_N$ are pairwise distinct.
3	26	There are at most two distinct values among $A_1,A_2,\cdots,A_N$ .
4	53	No additional constraints.

Samples

Input

1
7
1 1 2 2 3 3 3

Output

Pairing rice cakes with sizes $(1,2)$ , $(1,3)$ , and $(2,3)$ creates three bundles. The one remaining rice cake cannot form another bundle, so the maximum number is $3$ .

Editorial

View editorial