問題一覧 > 通常問題

No.120 Trends and Countermeasures: Kadomatsu Sequences (Part 1)

レベル : / AI推定難易度 : 825 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 231
作問者 : LayCurse
お気に入りにしたユーザー ProblemId : 291 / 自分の提出
問題文最終更新日: 2026-06-25 06:08:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 74 (順位表) の他の問題:

Problem Statement

Problems about kadomatsu sequences have been appearing frequently over the past few days.
Here, let us deepen our understanding of kadomatsu sequences through practice, so that we can solve them when such problems are set.
As all of you taking this kadomatsu sequence preparation course may already know, a kadomatsu sequence is a sequence of $3$ elements $a,b,c$ that satisfies the following $2$ conditions.
・$a,b,c$ are all distinct
・Among the $3$ elements, $b$ is the largest, or $b$ is the smallest

Now, Yuki has $N$ bamboo stalks, and the length of the $k$-th stalk is $L_k$.
Using these stalks, Yuki wants to make as many kadomatsu as possible.
Of course, $1$ kadomatsu uses $3$ stalks, and the lengths of those stalks must form a kadomatsu sequence.
The $3$ stalks to use may be chosen freely, and they may be freely rearranged to form a kadomatsu sequence.
Write a program that finds the maximum number of kadomatsu Yuki can make.
Although bamboo is said to grow quickly, it is a treasure of nature, so Yuki does not cut or join the stalks and uses them as they are.

Input

The $1$st line of the input contains the number of test cases $T$.
It is followed by $T$ test cases, given in the following format.

$N$
$L_1$ $L_2$ $\cdots$ $L_N$

$1 \leq T \leq 1000$
$1 \leq N \leq 100$
$1 \leq L_k \leq 1000000000 = 10^9$

Output

For each test case, output the maximum number of kadomatsu that can be made on $1$ line.

Sample

Sample 1
Input
1
3
1 2 3
Output
1

A kadomatsu sequence can be made using all $3$ stalks.
For example, $1,3,2$ or $2,1,3$ can be made.

Sample 2
Input
1
7
7 3 4 7 1 3 9
Output
2

$2$ kadomatsu sequences can be made; for example, using the first $3$ stalks and the next $3$ stalks in their given order gives the kadomatsu sequences $7,3,4$ and $7,1,3$.

Sample 3
Input
3
2
1 1
1
3
2
10 20
Output
0
0
0

A kadomatsu cannot be made without at least $3$ stalks.

Sample 4
Input
4
8
2 2 5 8 7 3 8 8
3
1 1 1
6
1 1 2 2 2 3
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output
2
0
1
5

Happy New Year.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。