The only difference between the easy version and the hard version of the problem is the constraints on $$$n$$$, $$$k$$$, and $$$a_i$$$.
It's the year 2125, and e-archaeologists have uncovered remnants of what they believe was known as the "troll face". They believe that the troll face was represented by a non-degenerate $$$k$$$-sided polygon that could be inscribed in a circle. Note that for this problem, $$$k$$$ is always 3.
So far, the e-archaeologists have discovered $$$n$$$ line segments, each of which has a length $$$a_i$$$. Now, the e-archaeologists are wondering: how many $$$k$$$-size subsets of their $$$n$$$ line segments could be used to create a troll face?
Consider all line segments to be unique, even if 2 have the same length.
The first line of input contains 2 integers, $$$n$$$ and $$$k$$$ ($$$3\le n\le 5000, \mathbf{k=3}$$$) — the number of line segments and the number of sides in a troll face, respectively.
The second line of input contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — the lengths of the $$$n$$$ line segments.
Output a single integer, the number of $$$k$$$-size subsets that could be used to create a troll face.,
5 31 2 3 3 3
7
In the first test case, there are 7 unique subsets (Note that all the 3's are considered to be distinct):
