class Solution {
    private fun countFairPairsBelow(
        nums: List<Int>,
        upper: Int,
    ): Long {
        var pairs = 0L

        var (left, right) = 0 to nums.size - 1
        while (left < right) {
            val sum = nums[left] + nums[right]

            if (sum < upper) {
                pairs += right - left
                left += 1
            } else {
                right -= 1
            }
        }

        return pairs
    }

    fun countFairPairs(
        nums: IntArray,
        lower: Int,
        upper: Int,
    ): Long {
        val sortedNums = nums.sorted()
        return (
            countFairPairsBelow(sortedNums, upper + 1) -
                countFairPairsBelow(sortedNums, lower)
        )
    }
}