<p>You are given three positive integers:&nbsp;<code>n</code>, <code>index</code>, and <code>maxSum</code>. You want to construct an array <code>nums</code> (<strong>0-indexed</strong>)<strong> </strong>that satisfies the following conditions:</p>

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>nums[i]</code> is a <strong>positive</strong> integer where <code>0 &lt;= i &lt; n</code>.</li>
	<li><code>abs(nums[i] - nums[i+1]) &lt;= 1</code> where <code>0 &lt;= i &lt; n-1</code>.</li>
	<li>The sum of all the elements of <code>nums</code> does not exceed <code>maxSum</code>.</li>
	<li><code>nums[index]</code> is <strong>maximized</strong>.</li>
</ul>

<p>Return <code>nums[index]</code><em> of the constructed array</em>.</p>

<p>Note that <code>abs(x)</code> equals <code>x</code> if <code>x &gt;= 0</code>, and <code>-x</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 4, index = 2,  maxSum = 6
<strong>Output:</strong> 2
<strong>Explanation:</strong> nums = [1,2,<u><strong>2</strong></u>,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 6, index = 1,  maxSum = 10
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= maxSum &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= index &lt; n</code></li>
</ul>

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def test(a):
            """
            b = a - index calculates the smallest possible value that could appear on the far left of the array 
            (at position 0) if the value decreased by 1 for each step leftward from index.
            The max(a - index, 0) ensures that b is non-negative (i.e., it cannot go below 0).
            Example:
            If a = 5 and index = 3, then the value at index - 3 would be 5 - 3 = 2.
            If index were greater than a, a - index would be negative, but since values can't be negative, b would be set to 0.
            """
            b = max(a - index, 0)

            """
            (a + b) represents the sum of the first and last terms.
            (a - b + 1) represents the total number of terms in the sequence.
            The product of these two values, divided by 2, gives the sum of the sequence.
            """
            res = (a + b) * (a - b + 1) / 2

            # Second Calculation: It computes the sum of the right side of the array 
            # starting from index + 1 to n - 1, where elements similarly decrease.
            b = max(a - ((n - 1) - index), 0)
            
            # The sum of the array is computed, and test(a) returns this value.
            # (excluding a itself because it was added twice)
            res += (a + b) * (a - b + 1) / 2
            return res - a

        """
        This is because the minimum value for each element in the array is 1 
        (as nums[i] must be a positive integer). If every element is set to 1, 
        the sum is already n. Hence, we work with maxSum - n to account for 
        the extra value we can distribute across the array.
        """
        maxSum -= n
        left, right = 0, maxSum
        """
        Use left = mid + 1, right = mid, return left when you're minimizing and 
        want to find the smallest possible value that satisfies the condition.

        Use left = mid, right = mid - 1, return left + 1 when you're maximizing 
        and want to find the largest possible value that satisfies the condition.
        """
        while left < right:
            mid = (left + right + 1) // 2
            print("test(mid): ", test(mid))
            print("maxSum:" ,maxSum)
            if test(mid) <= maxSum:
                left = mid
            else:
                right = mid - 1
            print("mid: ", mid)
           
            print("left: ", left)
            print("right: ", right)
            print("\n")
        return left + 1



        # Reference
        # class Solution:
        #     def shipWithinDays(self, weights: List[int], days: int) -> int:
        #         left, right = max(weights), sum(weights)

        #         while left < right:
        #             mid = left + (right-left)//2
        #             countWeight = 0
        #             countNum = 1
        #             for w in weights:
        #                 if countWeight + w > mid:
        #                     countNum += 1
        #                     countWeight = 0
        #                 countWeight += w
        #             print("mid: ", mid)
        #             print("countnum: ", countNum)
        #             print("days: ", days)
        #             if countNum > days:
        #                 left = mid + 1
        #             else:
        #                 right = mid
                
        #         return left

68