Counting Isosceles Triangles from Sticks

You are given n sticks labeled from 1 to n with lengths a₁, a₂, …, a_n. Your task is to count the number of ways to choose 3 distinct sticks such that they can form an isosceles triangle. In other words, the chosen 3 lengths (x, y, z) (in any order) must satisfy:

• Triangle inequality: every two sides sum to more than the third, i.e. x+y>z, y+z>x, and z+x>y.
• At least two sides are equal.

Note that an equilateral triangle (all three sides equal) is considered isosceles. Since the answer can be very large, output the result modulo 998244353.

The triangle conditions when the two equal sides have length \(x\) and the third side has length \(y\) (with \(x\neq y\)) boil down to:

[ 2x > y \quad (\text{and obviously } x+y > x \text{ holds}) ]

Input Example: For instance, if the stick lengths are {3, 3, 2, 2, 4, 5}, one valid set of choices is picking the sticks with indices \(\{1,2,3\}\) which correspond to lengths \(3,3,2\). In total there are 6 valid ways.

inputFormat

The first line contains a single integer n (the number of sticks).

The second line contains n space-separated integers a₁, a₂, ..., a_n representing the lengths of the sticks.

outputFormat

Output a single integer: the number of ways to choose 3 sticks that can form an isosceles triangle, taken modulo 998244353.

sample

6
3 3 2 2 4 5

6