Boards stand upright in a channel at positions 0, 1, ..., n - 1; board i has height
heights[i]. Sealing the channel with two boards i < j (the boards in between are lifted out)
makes a pool that holds min(heights[i], heights[j]) * (j - i) units of water.
Return a tuple (best, ways): best is the largest amount any pair can hold, and ways is the
number of pairs (i, j) with i < j that hold exactly best. With fewer than two boards
return (0, 0).
Examples
Input: heights = [3, 6, 2, 6, 3]
Output: (12, 2)
Explanation: (0, 4) holds 3 * 4 = 12 and (1, 3) holds 6 * 2 = 12. No pair holds more.
Input: heights = [4, 4, 4, 4]
Output: (12, 1)
Explanation: only the outer pair (0, 3) holds 4 * 3 = 12.
Input: heights = [1, 2, 3, 4, 3, 2, 1]
Output: (8, 1)
Explanation: (1, 5) holds 2 * 4 = 8.
Constraints
0 <= len(heights) <= 10**51 <= heights[i] <= 10**6- An O(n^2) check of every pair will time out on the largest tests.
Goals
- Argue exactly which pairs an inward scan may safely skip
- Use that argument to count every optimal pair, not just find one