<p>You are given a <strong>0-indexed</strong> array <code>nums</code> of integers.</p>

<p>A triplet of indices <code>(i, j, k)</code> is a <strong>mountain</strong> if:</p>

<ul>
	<li><code>i &lt; j &lt; k</code></li>
	<li><code>nums[i] &lt; nums[j]</code> and <code>nums[k] &lt; nums[j]</code></li>
</ul>

<p>Return <em>the <strong>minimum possible sum</strong> of a mountain triplet of</em> <code>nums</code>. <em>If no such triplet exists, return</em> <code>-1</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [8,6,1,5,3]
<strong>Output:</strong> 9
<strong>Explanation:</strong> Triplet (2, 3, 4) is a mountain triplet of sum 9 since: 
- 2 &lt; 3 &lt; 4
- nums[2] &lt; nums[3] and nums[4] &lt; nums[3]
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,4,8,7,10,2]
<strong>Output:</strong> 13
<strong>Explanation:</strong> Triplet (1, 3, 5) is a mountain triplet of sum 13 since: 
- 1 &lt; 3 &lt; 5
- nums[1] &lt; nums[3] and nums[5] &lt; nums[3]
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.
</pre>

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

<pre>
<strong>Input:</strong> nums = [6,5,4,3,4,5]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be shown that there are no mountain triplets in nums.
</pre>

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

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>8</sup></code></li>
</ul>

class Solution:
    # best solution O(n)
    def _get_prefix(self, nums: list[int]) -> list[int]:
        res, min_val = [], nums[0]
        for n in nums[1:-1]:
            if n < min_val:
                min_val = n
            res.append(min_val)
        return res

    def minimumSum(self, nums: list[int]) -> int:
        res = inf
        for pref, n, suff in zip(self._get_prefix(nums), nums[1:-1], self._get_prefix(nums[::-1])[::-1]):
            if pref < n > suff and (val:= pref + n + suff) < res:
                res = val
        return res if res < inf else -1
    # ====================== with built in heap ==========================
    # def minimumSum(self, nums: List[int]) -> int:
    #     right_heap = [(v, i+2) for i, v in enumerate(nums[2:])]
    #     heapq.heapify(right_heap)
    #     min_sum = float('inf')

    #     left_min = float('inf')
    #     right_min = (float('inf'), -1)

    #     for mid_i in range(1, len(nums)-1):
    #         left_min = min(left_min, nums[mid_i - 1])
    #         while right_min[1] <= mid_i:
    #             right_min = heapq.heappop(right_heap)

    #         if left_min < nums[mid_i] and right_min[0] < nums[mid_i]:
    #             curr_sum = left_min + nums[mid_i] + right_min[0]
    #             min_sum = min(curr_sum, min_sum)

    #     if min_sum == float('inf'):
    #         return -1
    #     return min_sum

    # ====================== with heap from scratch ======================
#     def minimumSum(self, nums: List[int]) -> int:
#         heap = [(nums[i], i) for i in range(1, len(nums))]
#         build_min_heap(heap)
#         min_sum = float('inf')
#         left_min = nums[0]ghjhjgh

#         right_min, heap = pop(heap)
#         for mid in range(1, len(nums)-1):
#             while right_min[1] <= mid:
#                 right_min, heap = pop(heap)

#             left_min = min(left_min, nums[mid-1])
            
#             if left_min < nums[mid] and right_min[0] < nums[mid]:
#                 curr_sum = left_min + nums[mid] + right_min[0]
#                 min_sum = min(min_sum, curr_sum)
            
#         if min_sum == float('inf'):
#             return -1
#         return min_sum

# def heapify(heap_input, parent_ind):
#     left_ind = parent_ind * 2 + 1
#     right_ind = parent_ind * 2 + 2

#     smallest = parent_ind
#     for ind in [right_ind, left_ind]:
#         if ind < len(heap_input) and heap_input[smallest][0] > heap_input[ind][0]:
#             smallest = ind
    
#     if smallest != parent_ind:
#         heap_input[smallest], heap_input[parent_ind] = heap_input[parent_ind], heap_input[smallest]

#         heapify(heap_input, smallest)

# def build_min_heap(heap_input):
#     # start from the first non-leaf node
#     for ind in range(len(heap_input)//2 - 1 , -1 ,-1):
#         heapify(heap_input, ind)

# def pop(heap):
#     min_val = heap[0]
#     heap[0] = heap[-1]
#     heap = heap[:-1]
#     heapify(heap, 0)

#     return min_val, heap
        
509