Problem Description

You are reading about concrete mathematics when construction work starts next to you. Finding the construction more interesting, you look out the window and notice some wooden sticks of varying lengths. Specifically, you see $n$ sticks numbered $1, 2, 3, \ldots, n$ with lengths $a_1, a_2, a_3, \ldots, a_n$. You wonder: how many ways can you pick three sticks such that they can form an isosceles triangle? You don't want the output number to be too large, so the final count should be modulo $998244353$.

An isosceles triangle is defined as having any two sides' sum greater than the third side and at least two sides of equal length.

For example, if the stick lengths are $\{3, 3, 2, 2, 4, 5\}$, you have 6 ways, selecting the sticks numbered as: $\{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 $a_1, a_2, a_3, \ldots, a_n$, representing the lengths of the sticks.

Output Format

A single number representing the total number of ways modulo $998244353$.

Sample Input and Output

Sample Input #1

6
3 3 2 2 4 5

Sample Output #1

6

Sample Input #2

6
1 1 4 5 1 4

Sample Output #2

5

Sample Input #3

6
2 2 2 2 2 2

Sample Output #3

20

Notes

• Subtask1 ($30$ pts): $1 \leq n \leq 200$.
• Subtask2 ($30$ pts): $1 \leq n \leq 2000$.
• Subtask3 ($20$ pts): All stick lengths are equal.
• Subtask4 ($20$ pts): No special restrictions.

For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 2 \times 10^5$ and $1 \leq a_i \leq 2 \times 10^5$.

见题面 Input 部分

见题面 Output 部分