Description

You are reading Concrete Mathematics when the construction site next to you starts working. You find watching their work more interesting, so you look out the window and notice some wooden sticks of different lengths. Specifically, you see $n$ sticks numbered $1,2,3,\ldots,n$, with lengths $a_1,a_2,a_3,\ldots,a_n$. A sudden idea comes to you: how many ways are there to take out $3$ sticks such that they can form an isosceles triangle? You do not want the output number to be too large, so the final count should be taken modulo $998244353$.

The requirements for an isosceles triangle are: the sum of any two sides is greater than the third side, and at least two sides have equal length.

For example, if the stick lengths are $\{3,3,2,2,4,5\}$, then you have $6$ ways. The chosen stick indices are: $\{1,2,3\}$, $\{1,2,4\}$, $\{1,2,5\}$, $\{1,2,6\}$, $\{1,3,4\}$, $\{2,3,4\}$.

Input Format

The first line contains a positive integer $n$, representing the number of sticks.

The second line contains $n$ positive integers, representing $a_1,a_2,a_3,\ldots,a_n$.

Output Format

Output one number: the total number of valid ways modulo $998244353$.

6
3 3 2 2 4 5

6

6
1 1 4 5 1 4

5

6
2 2 2 2 2 2

20

Hint

• Subtask 1 ($30$ pts): $1\leq n \leq 200$.
• Subtask 2 ($30$ pts): $1\leq n \leq 2000$.
• Subtask 3 ($20$ pts): All stick lengths are equal.
• Subtask 4 ($20$ pts): No special constraints.

For $100\%$ of the testdata: $1\leq n \leq 2\times 10^5$, $1\leq a_i \leq 2\times 10^5$.

Translated by ChatGPT 5