<p>There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he <strong>refuses to steal from adjacent homes</strong>.</p>

<p>The <strong>capability</strong> of the robber is the maximum amount of money he steals from one house of all the houses he robbed.</p>

<p>You are given an integer array <code>nums</code> representing how much money is stashed in each house. More formally, the <code>i<sup>th</sup></code> house from the left has <code>nums[i]</code> dollars.</p>

<p>You are also given an integer <code>k</code>, representing the <strong>minimum</strong> number of houses the robber will steal from. It is always possible to steal at least <code>k</code> houses.</p>

<p>Return <em>the <strong>minimum</strong> capability of the robber out of all the possible ways to steal at least </em><code>k</code><em> houses</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [2,3,5,9], k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,7,9,3,1], k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= (nums.length + 1)/2</code></li>
</ul>

class Solution:
    def validSearch(self, nums: List, valid_params: tuple) -> bool:
        target, k = valid_params
        t_list = []
        ans_cons = 0
        counter = 0
        for i in range(len(nums)):
            if nums[i] <= target:
                if t_list:
                    if len(t_list) >= 2 and t_list[-2][1] + 1 == t_list[-1][1] and t_list[-1][1] + 1 == i:
                        counter += 1
                        # ans_cons += 1
                        # t_list.append((nums[i], i))
                        # continue
                    elif t_list and t_list[-1][1] + 1 == i:
                        # ans_cons += int(counter / 2)
                        counter = 2
                        # ans_cons += 2
                    else:
                        # ans_cons += int(counter / 2)
                        ans_cons += int(counter / 2)
                        counter = 0
                # if t_list and t_list[-1][1] + 1 == i:
                #     ans_cons = 2 if ans_cons == 0 else ans_cons + 1
                t_list.append((nums[i], i))
        ans_cons += int(counter / 2)
        #return (int(ans_cons / 2) >= k) or (len(t_list) - int(ans_cons / 2) >= k)
        return (ans_cons >= k) or (len(t_list) - ans_cons >= k)
    def binSearch(self, nums: List, search_params: tuple, k: int) -> int:
        # lo, hi = search_params
        # if lo == hi:
        #     return hi
        # if hi - lo == 1:
        #     return lo if self.validSearch(nums, (lo, k)) else hi
        # mid = lo + int((hi - lo) / 2)
        # if self.validSearch(nums, (mid, k)):
        #     return self.binSearch(nums, (lo, mid), k)
        # return self.binSearch(nums, (mid, hi), k)
        lo, hi = search_params
        while (hi > lo):
            if hi - lo == 1:
                return lo if self.validSearch(nums, (lo, k)) else hi
            mid = lo + int((hi - lo) / 2)
            if self.validSearch(nums, (mid, k)):
                hi = mid
            else:
                lo = mid
        return hi

    def minCapability(self, nums: List[int], k: int) -> int:
        if k > len(nums):
            return 0
        return self.binSearch(nums, (min(nums), max(nums)), k)
        #[53, 6, 68, 49, 95, 31, 8, 37, 100, 69, 58, 61, 41, 32, 67, 28, 77, 19, 100, 61, 66, 68, 13, 72, 18, 13, 94, 63, 10, 38, 69, 57, 62, 92, 76, 21, 22, 98, 77, 56, 33, 26, 20, 29, 65, 18, 33, 77, 10, 31, 18, 77, 22, 17, 97, 82, 47, 10, 27, 48, 3, 6, 40, 31, 48, 61, 3, 36, 17, 64, 18, 80, 43, 72, 77, 11, 95, 40, 72, 57, 88, 26, 4, 44, 38, 61, 74, 31, 80, 37, 39, 34, 100, 26, 32, 11, 92, 17, 38, 52, 39, 87, 8, 94, 93, 3, 88, 61, 3, 84, 40, 67, 63, 56, 58, 28, 11, 54, 10, 2, 88, 26, 94, 34, 92, 44, 19, 79, 88, 60, 10, 47, 3, 75, 59, 33, 56, 85, 67, 38, 7, 93, 70, 30, 29, 7, 53, 87, 97, 80, 99, 68, 80, 46, 90, 31, 39, 59, 55, 15, 91, 18, 96, 20, 25, 57, 88, 43, 53, 80, 80, 18, 69, 21, 37, 12, 23, 72, 60, 27, 91, 43, 2, 49, 67, 56, 47, 40, 60, 46, 23, 78, 84, 72, 97, 64, 4, 30, 70, 41, 79, 67, 96, 86, 29, 57, 59, 66, 21, 41, 94, 87, 26, 91, 97, 56, 65, 83, 25, 58, 44, 53, 100, 30, 15, 45, 47, 94, 31, 88, 42, 81, 5, 44, 43, 90, 56, 24, 33, 66, 49, 78, 34, 88, 86, 11, 94, 25, 86, 55, 93, 64, 2, 16, 97, 49, 39, 100, 65, 34, 96, 31, 46, 10, 29, 66, 18, 96, 100, 30, 31, 54, 16, 23, 2, 96, 7, 68, 9, 3, 61, 29, 9, 17, 59, 32, 11, 33, 72, 13, 56, 24, 80, 84, 42, 96, 35, 33, 41, 83, 19, 7, 40, 87, 40, 81, 54, 24, 71, 74, 44, 96, 73, 45, 8, 39, 37, 64, 87, 9, 53, 22, 92, 37, 81, 50, 19, 5, 24, 17, 18, 7, 20, 19, 68, 88, 66, 26, 40, 90, 65, 90, 75, 95, 13, 23, 94, 80, 96, 73, 2, 48, 2, 57, 95, 24, 100, 89, 35, 62, 65, 82, 39, 72, 86, 78, 94, 70, 99, 25, 22, 4, 36, 54, 87, 56, 71, 33, 81, 51, 87, 92, 69, 25, 99, 24, 75, 65, 42, 81, 56, 72, 64, 97, 97, 4, 87, 69, 69, 63, 42, 27, 45, 68, 21, 54, 20, 47, 38, 29, 48, 99, 28, 33, 44, 13, 34, 45, 57, 57, 67, 79, 2, 46, 52, 78, 4, 75, 35, 9, 28, 77, 57, 90, 36, 75, 94, 100, 51, 71, 35, 67, 38, 52, 98, 87, 56, 17, 16, 35, 89, 54, 3, 64, 38, 51, 19, 45, 5, 23, 59, 93, 8, 35, 40, 52, 12, 10, 12, 70, 78, 14, 25, 79, 61, 58, 95, 75, 65, 19, 59, 69, 3, 25, 80, 43, 69, 83, 26, 51, 35, 23, 75, 68, 20, 39, 59, 21, 75, 44, 69, 21, 88, 65, 38, 90, 38, 57, 28, 2, 94, 48, 29, 64, 40, 6, 39, 88, 46, 9, 57, 5, 90, 8, 24, 25, 19, 23, 15, 55, 80, 28, 62, 20, 70, 67, 2, 60, 22, 8, 7, 44, 71, 99, 47, 13, 38, 66, 45, 80, 31, 46, 11, 54, 89, 84, 64, 82, 68, 74, 48, 90, 18, 75, 15, 39, 71, 8, 51, 44, 76, 42, 41, 20, 68, 28, 73, 72, 76, 28, 5, 81, 65, 23, 45, 72, 60, 3, 14, 33, 97, 15, 59, 14, 54, 50, 65, 17, 8, 17, 17, 73, 91, 59, 17, 67, 47, 50, 32, 13, 38, 6, 34, 94, 17, 76, 87, 24, 61, 36, 84, 36, 69, 9, 41, 91, 74, 100, 13, 73]
        #[53, 6, 68, 49, 95, 31, 8, 37, 100, 69, 58, 61, 41, 32, 67, 28, 77, 19, 100, 61, 66, 68, 13, 72, 18, 13, 94, 63, 10, 38, 69, 57, 62, 92, 76, 21, 22, 98, 77, 56, 33, 26, 20, 29, 65, 18, 33, 77, 10, 31, 18, 77, 22, 17, 97, 82, 47, 10, 27, 48, 3, 6, 40, 31, 48, 61, 3, 36, 17, 64, 18, 80, 43, 72, 77, 11, 95, 40, 72, 57, 88, 26, 4]
        #[53, 6, 68, 49, 95, 31, 8, 37, 100, 69, 58, 61, 41, 32, 67, 28, 77, 19, 100, 61, 66, 68, 13, 72]

29100