From LeetCode. Counting horizontal trapezoids. Solve the geometry problem "Count Number of Trapezoids I".
Examples
Input:[1,2,3]
Output:0
Input:[2,3,4]
Output:0
Hints
Horizontal trapezoid needs two sides parallel to x-axis. Points with same y-coordinate form a horizontal line. Group points by y — each group gives candidate horizontal edges.
For y-level with v points, number of horizontal edges = v*(v-1)/2. Count trapezoids by pairing edges from different y-levels: accumulate product of edge counts between current y-level and all previous y-levels.
Order of y-levels processed doesn't matter — running sum of previous edge counts gives all pairs exactly once. Modulo 1e9+7. Single y-level insufficient (need two distinct y-levels for two horizontal sides).
Count Number of Trapezoids I
**From LeetCode.** Counting horizontal trapezoids. Solve the geometry problem "Count Number of Trapezoids I".