問題一覧 > 通常問題

No.120 傾向と対策:門松列(その1)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 171
作問者 : LayCurseLayCurse
7 ProblemId : 291 / 出題時の順位表
問題文最終更新日: 2016-05-24 14:36:40

問題文

ここ数日で門松列に関する問題が頻出しております.
ここでは演習を通じて,門松列に対する理解を深め,門松列の問題が出題された時に解けるようになっておきましょう.
門松列対策講座を受講される皆様は既にご存知かと思いますが,門松列とは $3$ 個の要素からなる数列 $a,b,c$ で以下の $2$ つの条件を満たすものです.
・$a,b,c$ は全て異なる
・$3$ つの要素の中で $b$ が最も大きい,または,$b$ が最も小さい

さて,雪さんは $N$ 本の竹を持っていて,$k$ 番目の竹の長さは $L_k$ です.
雪さんは,この竹を使って,できるだけ多くの門松を作りたいです.
勿論,$1$ 個の門松には,$3$ 本の竹を使い,その竹の長さは門松列でなければいけません.
使う $3$ 本の竹は自由に選んでよく,また門松列にするために自由に並び替えて良いです.
雪さんは,最大でいくつの門松を作ることができるかを求めるプログラムを書いてください.
竹はすぐ育つとは言いますが,自然の宝であり,切ったり繋げたりすることはせず,雪さんはこれらの竹をそのまま使用します.

入力

入力の $1$ 行目にはテストケースの数 $T$ が書かれています.
それに続き,$T$ 個のテストケースが以下の形式で与えられます.

$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$

出力

各テストケースに対して,作れる門松の数の最大値を $1$ 行で出力してください.

サンプル

サンプル1
入力
1
3
1 2 3
出力
1

$3$ 本の竹を全て使い門松列を作ることができます.
例えば,$1,3,2$ とか $2,1,3$ とかが作れます.

サンプル2
入力
1
7
7 3 4 7 1 3 9
出力
2

$2$ つの門松列,例えば,最初の $3$ 本と次の $3$ 本をそのままの順番で用いて $7,3,4$ と $7,1,3$ という門松列を作れます.

サンプル3
入力
3
2
1 1
1
3
2
10 20
出力
0
0
0

最低でも竹が $3$ 本ないと門松は作れません.

サンプル4
入力
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
出力
2
0
1
5

新年あけましておめでとうございます.

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