<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:
        
        # base = (maxSum // n) - 1
        #  nums = [base] * n
        # currSum = base * n
        
        # leftovers = (maxSum % n) + n
        # if leftovers == 0:
        #     return nums[index]

        # Maybe divide the remainder up between the sides and allocate?
        partitions = 1
        left_diff = index
        # if left_diff > 0:
        #     partitions += 1
        right_diff = n - index - 1
        # if right_diff > 0:
        #     partitions += 1

        # split = leftovers // partitions
        # left_split, middle_split, right_split = 0, split, 0
        # if left_diff > 0:
        #     left_split = split
        # if right_diff > 0:
        #     right_split = split
        
        # remainder = leftovers % partitions
        # if remainder == 1:
        #     middle_split += 1
        # elif remainder == 2:
        #     # allocate to right instead of left depending on which diff is bigger
        #     left_split += 1
        #     middle_split += 1
        
        

        # nums[index] += middle_split
        # left_split = 
        # left_diff = 2
        # right_split = 2


        def isValid(mid_value):
            # a - first term
            # d - common difference
            # x - # of terms
            # Calculate Arithmetic Sum of both sides, excluding index.
            print("target mid_value: " + str(mid_value))
            print("left diff: " + str(left_diff))
            print("right diff: " + str(right_diff))

            arith_sum_left, arith_sum_right = 0, 0
            if left_diff == 0:
                arith_sum_left = 0 #nums[0]
            else:
                start_value = (mid_value - left_diff)
                diff = left_diff
                ones = 0
                if start_value <= 0:
                    start_value = 1
                    diff = mid_value - 1
                    ones = (left_diff - mid_value) + 1
                a, d, x = start_value, 1, diff
                arith_sum_left = ((x / 2) * (2 * a + (x - 1) * d))
                print("arith_sum_left: " + str(arith_sum_left))
                arith_sum_left += ones
                print("udpated arith_sum_left: " + str(arith_sum_left))

            if right_diff == 0:
                arith_sum_right = 0 #nums[index + 1]   
            else:
                start_value = (mid_value - right_diff)
                diff = right_diff
                ones = 0
                if start_value <= 0:
                    start_value = 1
                    diff = mid_value - 1
                    ones = (right_diff - mid_value) + 1
                a, d, x = start_value, 1, diff
                arith_sum_right = ((x / 2) * (2 * a + (x - 1) * d))
                print("arith_sum_right: " + str(arith_sum_right))
                arith_sum_right += ones
                print("udpated arith_sum_right: " + str(arith_sum_right))

            # if ((arith_sum_left >= left_split) and (arith_sum_right >= right_split) 
            # and (arith_sum_left + arith_sum_right + mid_value <= maxSum)):
            print("SUM: " + str(arith_sum_left + arith_sum_right + mid_value))
            print("SUM <= maxSum: " + str(arith_sum_left + arith_sum_right + mid_value <= maxSum))
            if (arith_sum_left + arith_sum_right + mid_value <= maxSum):
                print("TRUE! ")
                return True
            
            return False

        # ranges = list(range(1, maxSum + 1))
        l, r = 0, maxSum
        largest = 0
        while l <= r:
            curr = (l + r) // 2
            if curr == 0:
                return 1
            print("-------------")
            print("curr: " + str(curr))

            check = isValid(curr)
            if check:
                largest = max(largest, curr)
                l = curr + 1
            else:
                r = curr - 1
        
        return largest

        
            

        """


        [5, 6, 7]
        n = 3
        index = 2
        maxSum = 18
        """

        """
        [1, 1, 1, 1, 1, 1]
        leftovers = 4
        index = 1

        left_diff = 1
        right_diff = 5

        left_split = 1
        middle_split = 2
        right_split = 1

        # a - first term
        # d - common difference
        # x - # of terms
        a, d, x = nums[0], 1, left_diff
        arith_sum_left = ((x / 2) * (2 * a + (x - 1) * d))
        a, d, x = nums[index + 1], 1, right_diff
        arith_sum_right = ((x / 2) * (2 * a + (x - 1) * d))

        """







            
        

        
        # while leftovers != 0:
        #     split = leftovers // 3
        #     remainder = leftovers % 3
        #     left



        # Repeat
            # Update the nums[index]
            # Validate left side (search left)
            # Validate right side







        """

        curr = index
        while True:
            if remainder != 0:
                nums[curr] += 1
                remainder -= 1
                
            
                if curr - 1 >= 0:
                    curr -= 1
                
        """



        
82