class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        # We can find the global maximum and minimum of the entire array using built-in functions.
        # The time complexity of max() and min() is O(N) each, making the total O(N).
        max_val = max(nums)
        min_val = min(nums)

        # The optimal approach is to pick the entire array exactly k times.
        # This gives us the absolute maximum difference possible.
        # Python automatically handles arbitrarily large integers, so no overflow concerns.
        return k * (max_val - min_val)

class Solution {
    public long maxTotalValue(int[] nums, int k) {
        // Initialize max and min values with the first element of the array
        int maxVal = nums[0];
        int minVal = nums[0];

        // Iterate through the array to find the global maximum and minimum
        for (int num : nums) {
            if (num > maxVal) {
                maxVal = num;
            }
            if (num < minVal) {
                minVal = num;
            }
        }

        // The maximum value for a single subarray is maxVal - minVal.
        // We multiply this by k to get the maximum total value.
        // Cast k to a long before multiplication to prevent 32-bit integer overflow.
        return (long) k * (maxVal - minVal);
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxTotalValue = function(nums, k) {
    // Initialize the global extreme values
    let maxVal = nums[0];
    let minVal = nums[0];

    // Iterate through the array once to find the global max and min.
    // We do not use Math.max(...nums) because it can throw a Maximum Call Stack Size 
    // Exceeded error if the array is very large (e.g. 50,000 elements).
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
        if (nums[i] < minVal) minVal = nums[i];
    }

    // Return the difference multiplied by k.
    // JS numbers are double-precision floats, which safely represent integers up to 2^53 - 1.
    // Our max possible answer is 10^14, which fits comfortably without needing BigInt.
    return k * (maxVal - minVal);
};

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        // Initialize max and min with the first element
        int maxVal = nums[0];
        int minVal = nums[0];

        // Find the global maximum and minimum in the array
        for (int num : nums) {
            if (num > maxVal) maxVal = num;
            if (num < minVal) minVal = num;
        }

        // We choose the entire array k times.
        // The maximum possible value is 10^14, which exceeds the 32-bit int limit.
        // So we cast k to long long to perform 64-bit arithmetic.
        return (long long) k * (maxVal - minVal);
    }
};

public class Solution {
    public long MaxTotalValue(int[] nums, int k) {
        // Initialize the extreme values using the first element
        int maxVal = nums[0];
        int minVal = nums[0];

        // Iterate over all elements to find the global maximum and minimum
        foreach (int num in nums) {
            if (num > maxVal) maxVal = num;
            if (num < minVal) minVal = num;
        }

        // Since max difference is 10^9 and k is 10^5, the product can be 10^14.
        // We explicitly cast to long to avoid 32-bit integer overflow.
        return (long) k * (maxVal - minVal);
    }
}

func maxTotalValue(nums []int, k int) int64 {
    // Start by assuming the first element is both the max and the min
    maxVal := nums[0]
    minVal := nums[0]

    // Make a single pass through the array to update max and min
    for _, num := range nums {
        if num > maxVal {
            maxVal = num
        }
        if num < minVal {
            minVal = num
        }
    }

    // Calculate the difference and multiply by k.
    // Cast everything to int64 to avoid overflow since the answer can be up to 10^14.
    return int64(k) * int64(maxVal - minVal)
}

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def max_total_value(nums, k)
    # Ruby arrays have highly optimized built-in methods for max and min.
    # We find the global maximum and minimum.
    max_val = nums.max
    min_val = nums.min

    # We can pick the entire array exactly k times to get the maximum sum.
    # Ruby automatically handles large integers seamlessly, so no overflow occurs.
    k * (max_val - min_val)
end

impl Solution {
    pub fn max_total_value(nums: Vec<i32>, k: i32) -> i64 {
        // Initialize max and min with the first element of the array
        let mut max_val = nums[0];
        let mut min_val = nums[0];

        // Iterate through the array to find the global extreme values
        for &num in nums.iter() {
            if num > max_val { max_val = num; }
            if num < min_val { min_val = num; }
        }

        // Calculate the maximum difference
        let diff = (max_val - min_val) as i64;

        // Multiply by k using 64-bit integer arithmetic to prevent overflow
        (k as i64) * diff
    }
}

class Solution {
    fun maxTotalValue(nums: IntArray, k: Int): Long {
        // Assume the first element is both the minimum and maximum
        var maxVal = nums[0]
        var minVal = nums[0]

        // Iterate through all elements to find the global max and min
        for (num in nums) {
            if (num > maxVal) maxVal = num
            if (num < minVal) minVal = num
        }

        // Cast k and the difference to Long to prevent 32-bit integer overflow.
        // The max possible value is 10^14.
        return k.toLong() * (maxVal - minVal).toLong()
    }
}

class Solution {
    func maxTotalValue(_ nums: [Int], _ k: Int) -> Int {
        // Initialize extremes using the first element
        var maxVal = nums[0]
        var minVal = nums[0]

        // Single pass to find the global maximum and minimum
        for num in nums {
            if num > maxVal { maxVal = num }
            if num < minVal { minVal = num }
        }

        // Swift's Int is 64-bit on 64-bit platforms, which safely holds 10^14.
        // Simply return the difference multiplied by k.
        return k * (maxVal - minVal)
    }
}