問題一覧 > 通常問題

No.118 Kadomatsu Sequence (2)

レベル : / AI推定難易度 : 450 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 274
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 221 / 自分の提出
問題文最終更新日: 2026-06-25 06:09:56
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 73 (順位表) の他の問題:

Problem Statement

While making a kadomatsu to decorate the entrance, I noticed something.

Given $N$ bamboo stalks with heights $A_i$,
you may freely choose $3$ of them and freely rearrange them.
I became curious how many of the ways of choosing form a "Kadomatsu Sequence".

A "Kadomatsu Sequence" is defined as one that satisfies both of the conditions "among the $3$ chosen bamboo stalks, the $2$nd in descending order of length is on the left or right side" and "the $3$ lengths are all different".

Given the heights of the $N$ bamboo stalks, find the number of ways to choose 3 bamboo stalks that can form a "Kadomatsu Sequence".
(The same combination of bamboo stalks is counted as the same, even if the order differs.)

Since the answer can exceed the range of int (though it apparently does not exceed that of long), find the value $\rm mod\ 10^9+7$.

Each bamboo stalk is numbered, so they are distinguishable.

Input

$N$
$A_1\ A_2 \dots A_N$

All inputs are given as integers.
$3\le N \le 100000=10^5$
$1\le A_i \le 100=10^2,1\le i \le N$

Output

Output the number of combinations that form a "Kadomatsu Sequence", $\rm mod\ 10^9+7$.

Sample

Sample 1
Input
3
1 2 3
Output
1

These 3 bamboo stalks can form a Kadomatsu Sequence.

Sample 2
Input
6
1 2 2 3 3 3
Output
6

The bamboo stalks of length 2 and those of length 3 are each distinguishable, so there appear to be 6 ways of choosing.

Sample 3
Input
10
13 54 87 47 99 33 2 56 95 85
Output
120

In this case, the answer is the same as ${}_{10} C_3$.

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