Given an integer array bloomDay, an integer m and an integer k.
We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
 
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:
Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:
Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

 
Constraints:

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

Difficulty: interview

Starter code:

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

Solutions:
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        flowersN = len(bloomDay)
        if flowersN < m*k:
            return -1
        
        def checkFlowers(x):
            count = 0
            gotFlowers = 0
            for num in bloomDay:
                if num <= x:
                    count += 1
                    if count == k:
                        gotFlowers += 1
                        count = 0
                else:
                    count = 0
            # print(gotFlowers, x, m)
            return gotFlowers >= m
        
        sortedDays = sorted(list(set(bloomDay)))
        l = 0
        r = len(sortedDays) - 1
        if checkFlowers(sortedDays[l]):
            return sortedDays[l]
        while l < r:
            mm = (l + r)//2
            if checkFlowers(sortedDays[mm]):
                r = mm
            else:
                l = mm+ 1
        return sortedDays[l]

class Solution:
    def minDays(self, arr: List[int], m: int, k: int) -> int:
        def count(arr, x, k):
            out = 0
            count = 0
            for i in arr:
                if i <= x:
                    count += 1
                    if count == k:
                        out += 1
                        count = 0
                else:
                    count = 0

            return out
        
        if len(arr) < m*k:
            return -1
        res = -1
        bi = list(sorted(set(arr)))
        start = 0
        end = len(bi)-1
        while start <= end:
            mid = (start+end)//2
            if count(arr, bi[mid], k) >= m:
                res = bi[mid]
                end = mid - 1
            else:
                start = mid + 1

        return res


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        
        def invalid(threshold):
            cur = 0
            bouquets = 0
            for x in bloomDay:
                if x <= threshold:
                    cur += 1
                else:
                    bouquets += cur // k
                    cur = 0
            bouquets += cur // k
            return bouquets < m
        
        left, right = 1, max(bloomDay)
        while left <= right:
            mid = (left + right) // 2
            # print(left, right, mid)
            if invalid(mid):
                left = mid + 1
            else:
                right = mid - 1
        return left

class Solution:
    def minDays(self, arr: List[int], m: int, k: int) -> int:
        l, r, n = 0, max(arr) + 1, len(arr)
        if m * k > n: return -1
        while l < r:
            mid = l + (r - l) // 2
            cnt, tmp = 0, 0
            for i, v in enumerate(arr):
                cnt = 0 if v > mid else cnt + 1
                if cnt == k:
                    tmp += 1
                    cnt = 0
                    if tmp == m: break
            if tmp == m:
                r = mid
            else:
                l = mid + 1
        return l


class Solution:
    def checkDay(self,day,bloomDay,m,k)->bool:
        y,count=0,0
        for i in range(len(bloomDay)):
            if bloomDay[i] <= day:
                #bloomed.append(1)
                y+=1
            else:
                #bloomed.append(0)
                y=0
            if y==k:
                count+=1
                y=0
            if count==m:
                return True
        return False
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        '''
        bloomDay: Flower garden, elements are # of days required for that flower to bloom
        m: # of bouquets needed
        k: # of adjacent flowers needed in each bouquet
        First, check to see if mk>len(bloomDay). If so return -1
        Then, see how many days needed until mk flowers have bloomed
            Check to see if they are adjacent
            if so return days
            else maybe check how many adjacents are needed, or go to the next day
        
        '''
        #bloomDay,m,k = [7,7,7,7,12,7,7],2,3
        
        FN=m*k # (Flowers Needed)
        if FN > len(bloomDay):
            return -1
        
        
        # After x days, is it possible to create m bouquets?
        
        
        bloomed=sorted(set(bloomDay))
        lastWorking,count,start,stop=-1,0,0,len(bloomed)
        #print(bloomed)
        half=stop//2
        #day=bloomed[half]
        while(start<=half<stop):
            day=bloomed[half]
            #print('Half: ',half,', Day: ',day,' || Bounds: ',start,', ',stop)
            
            # If current day works, check previous day
            if self.checkDay(day,bloomDay,m,k):
                #print('Day:  ',day,' works')
                lastWorking,stop=day,half
            # Otherwise check half of new bounds
            else:
                start=half+1
            half=(start+stop)//2
            
        return lastWorking

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m*k:
            return -1
        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right-left) // 2
            if self.__feasible(bloomDay, k, m, mid):
                right = mid
            else:
                left = mid+1
        return left
    
    def __feasible(self, bloomDay, k, m, day):
        bloom = [day >= bloom_day for bloom_day in bloomDay]
        cnt = 0
        accu = 0
        for b in bloom:
            if b:
                accu += 1
                if accu == k:
                    cnt += 1
                    accu = 0
            else:
                accu = 0
        return cnt >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMakeBouquets(cap):
            nBouquets = 0
            nFlowers = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] > cap:
                    nFlowers = 0
                    continue
                nFlowers += 1
                if nFlowers == k:
                    nBouquets += 1
                    nFlowers = 0
            return nBouquets >= m
        
        if m*k > len(bloomDay):
            return -1
        
        lo, hi = min(bloomDay), max(bloomDay)
        while lo < hi:
            med = lo + (hi-lo)//2
            if canMakeBouquets(med):
                hi = med
            else:
                lo = med + 1
        return hi

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def bouquet_count(t):
            count = 0
            res = 0
            for i in range(n):
                if bloomDay[i] <= t:
                    count += 1
                    if count == k:
                        count = 0
                        res += 1
                else:
                    count = 0
            return res
        
        n = len(bloomDay)
        if m * k > n:
            return -1
        
        low, high = min(bloomDay), max(bloomDay)
        
        while low <= high:
            mid = low + (high - low) // 2
            if bouquet_count(mid) >= m:
                high = mid - 1
            else:
                low = mid + 1
                
        return low

class Solution:
    def checkDay(self,day,bloomDay,m,k)->bool:
        y,count=0,0
        for i in range(len(bloomDay)):
            if bloomDay[i] <= day:
                #bloomed.append(1)
                y+=1
            else:
                #bloomed.append(0)
                y=0
            if y==k:
                count+=1
                y=0
            if count==m:
                return True
        return False
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        '''
        bloomDay: Flower garden, elements are # of days required for that flower to bloom
        m: # of bouquets needed
        k: # of adjacent flowers needed in each bouquet
        First, check to see if mk>len(bloomDay). If so return -1
        Then, see how many days needed until mk flowers have bloomed
            Check to see if they are adjacent
            if so return days
            else maybe check how many adjacents are needed, or go to the next day
        
        '''
        #bloomDay,m,k = [7,7,7,7,12,7,7],2,3
        
        FN=m*k # (Flowers Needed)
        if FN > len(bloomDay):
            return -1
        
        
        # After x days, is it possible to create m bouquets?
        lastWorking,count,start,stop=-1,0,0,len(bloomDay)
        bloomed=sorted(bloomDay)
        print(bloomed)
        half=stop//2
        #day=bloomed[half]
        while(start<=half<stop):
            day=bloomed[half]
            print('Half: ',half,', Day: ',day,' || Bounds: ',start,', ',stop)
            
            # If current day works, check previous day
            if self.checkDay(day,bloomDay,m,k):
                print('Day:  ',day,' works')
                lastWorking,stop=day,half
            # Otherwise check half of new bounds
            else:
                start=half+1
            half=(start+stop)//2
            
        return lastWorking

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left = min(bloomDay)
        right = max(bloomDay)
        n = len(bloomDay)
        if m*k > n:
            return -1
        
        while left <= right:
            mid = (left + right)//2
            c = 0
            bout = m
            print((left, mid, right))
            for b in bloomDay:
                if b <= mid:
                    c += 1
                else:
                    c = 0
                if c >= k: 
                    bout -= 1
                    c -= k
                    if bout == 0: break
            if bout == 0: right = mid - 1
            else: left = mid + 1
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        l = 1
        r = max(bloomDay)
        while l < r:
            mid = (l + r) // 2
            flow = 0
            nums = 0
            for i in range(len(bloomDay)):
                if nums >= m:
                    break
                if bloomDay[i] > mid:
                    flow = 0
                else:
                    flow += 1
                    if flow >= k:
                        flow = 0
                        nums += 1
            # print(mid, nums)
            if nums >= m:
                r = mid
            else:
                l = mid + 1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        n=len(bloomDay)
        def counter(day, k):
            count, bouquets = 0, 0
            for i in range(n):
                if bloomDay[i]<=day:
                    count+=1
                else:
                    count=0
                if count==k:
                    bouquets+=1
                    count=0
            return bouquets
        low, high = 1, max(bloomDay)
        while(low<high):
            mid=(low+high)//2
            if counter(mid, k) >= m:
                high = mid
            else:
                low=mid+1
        return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        lower_bound = min(bloomDay)
        upper_bound = max(bloomDay)
        while lower_bound < upper_bound:
            days = (lower_bound + upper_bound) // 2
            if self.can_make_bouquets(bloomDay, m, k, days):
                upper_bound = days
            else:
                lower_bound = days + 1
                
        return upper_bound
    
    def can_make_bouquets(self, bloomDay, m, k, days):
        bouquets_made = 0
        adj_count = 0
        
        K = k
        for i in range(len(bloomDay)):
            if bloomDay[i] <= days:
                K -= 1
            else:
                K = k
            
            if K == 0:
                bouquets_made += 1
                K = k
                
        return bouquets_made >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        tmp = sorted(list(set(bloomDay)))
        low = 0
        high = len(tmp) - 1

        def feasible(val):
            count = 0
            total = m

            for day in bloomDay:
                if val >= day:
                    count += 1
                    
                    if count == k:
                        total -= 1
                        count = 0

                        if total == -1:
                            break

                else:
                    count = 0
                

            return total <= 0
            

        while low < high:
            mid = (low + high) // 2
            val = tmp[mid]

            if feasible(val):
                high = mid
            else:
                low = mid + 1
        
        return tmp[low]

class Solution:
    def minDays(self, F: List[int], m: int, k: int) -> int:
        
        if(m*k>len(F)):
            return -1
        
        ans = 0
        
        left = 1
        right = max(F)
        while(left<=right):
            mid = (left+right)//2
            
            if(self.possible(mid,F,m,k)==True):
                ans = mid
                right = mid-1
                
            else:
                left=mid+1
                
        return ans
    
    
    def possible(self,mid,F,m,k):
        # print(mid)
        count = 0
        a = 0
        for i in range(len(F)):
            if(a==k):
                count+=1
                a=0
                
            if(F[i]<=mid):
                a+=1
            else:
                a = 0
        if(a==k):
            count+=1
                
        if(count>=m):
            return True
        return False

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m*k > n:
            return -1
        
        def can_make_bouquets(m: int, k: int, day: int) -> bool:
            #print(m, k, day)
            total_bouquets = 0
            curr_flowers = 0
            for index, d in enumerate(bloomDay):
                if total_bouquets + 1 + (n-index-1)//k < m:
                    #print(\"No\")
                    return False
                if d <= day:
                    curr_flowers += 1
                    if curr_flowers == k:
                        total_bouquets += 1
                        curr_flowers = 0
                else:
                    curr_flowers = 0
                if total_bouquets == m:
                    #print(\"Yes\")
                    return True
            return False
        
        days = sorted(list(set(bloomDay)))
        lo, hi = 0, len(days)-1
        min_days = float('inf')
        #print(days)
        while lo <= hi:
            mi = (lo+hi)//2
            #print(lo, mi, hi)
            if can_make_bouquets(m, k, days[mi]):
                min_days = min(min_days, days[mi])
                hi = mi-1
            else:
                lo = mi+1
        
        return min_days if min_days < float('inf') else -1
                
            


class Solution:
    def minDays(self, blooms: List[int], m: int, k: int) -> int:
        def check(d):
            bouq, b = 0, 0
            for i in range(len(blooms)):
                if blooms[i] <= d:
                    b += 1
                else:
                    b = 0
                if b == k:
                    b = 0
                    bouq += 1
                    if bouq >= m:
                        return True
            return bouq >= m
        
        lo, hi = 1, max(blooms)
        while lo < hi:
            mid = (hi+lo)//2
            if not check(mid):
                lo = mid + 1
            else: hi = mid
        return lo if check(lo) else -1


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m*k: return -1
        def count(day):
            cnt,counter=0,0
            for i in range(n):
                if bloomDay[i]<=day:
                    counter +=1
                    if counter ==k:
                        cnt +=1
                        counter = 0
                else:
                    counter =0
            return cnt
        l,r = min(bloomDay),max(bloomDay)
        while l<=r:
            mid = l+(r-l)//2
            if count(mid) <m:
                l = mid+1
            else:
                r = mid -1
        return l
                
            
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def bouquets_possible(day):
            bouquets_count = 0
            conse_day = 0
            for i, v in enumerate(bloomDay):
                if v <= day:
                    conse_day += 1
                    if conse_day == k:
                        bouquets_count += 1
                        conse_day = 0
                else:
                    conse_day = 0
            return bouquets_count
        
        if len(bloomDay) < m * k:
            return -1
        
        left = min(bloomDay)
        right = max(bloomDay)
        
        while left < right:
            mid = left + ( right - left)//2
            if bouquets_possible(mid) < m:
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # min -> 0 max - > max(element)
        # check for m*k and valid check kar
        # condition main keep checking the consecutive flowers
        # m -> m bouqets , k adjacent flower
        # if len(bloomDay)<m*k:
        #     return -1
        
        def isPossible(t):
            count = 0
            res = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] <= t:    
                    count += 1
                    if count == k:
                        count = 0
                        res += 1
                else:
                    count = 0
            return res>=m
        
        s,e = 0, max(bloomDay)+1
        
        while s<e:
            mid = (s+e)//2
            if isPossible(mid):
                e = mid
            else:
                s = mid+1
                
        if s==max(bloomDay)+1:
            return -1
        
        return s

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if k*m > len(bloomDay): 
            return -1
        
        def isPossible(mid): 
            numFlowers = 0
            numBouquets = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] > mid:
                    numFlowers = 0
                else:
                    numFlowers += 1
                    if numFlowers >= k:
                        numBouquets += 1
                        numFlowers -= k
            
            # print(mid, numBouquets)
            return numBouquets >= m
        
        low = 0
        high = max(bloomDay)
        while (low < high):
            mid = int((low + high)/2)
            if (isPossible(mid)):
                # print(\"true\", mid)
                high = mid
            else:
                low = mid + 1
        return low 
                
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(days_cand):
            nonlocal bloomDay
            nonlocal m
            nonlocal k
            nonlocal res

            bukets = 0
            flowers_per_cur_bucket = 0

            for i in range(len(bloomDay)):
                today = bloomDay[i]
                if today <= days_cand:
                    #is flower
                    flowers_per_cur_bucket +=1
                    if flowers_per_cur_bucket == k:
                        bukets +=1
                        flowers_per_cur_bucket = 0
                        if bukets == m:
                            res = min(res, days_cand)                        
                            return True
                    pass
                else:
                    #no flower today
                    flowers_per_cur_bucket = 0
                    pass
            return False        


        res = float('inf')   
        left = min(bloomDay)
        right = max(bloomDay)+1

        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                # add to answer, check if can do better decrease mid and look up in left part
                right = mid
            else:
                left = mid + 1            
        if res < float('inf'):
            return left
        return -1   


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        flowers = collections.defaultdict(list)
        for idx, day in enumerate(bloomDay):
            flowers[day].append(idx)
        root = list(range(n))
        num_flowers_left = collections.Counter()
        num_flowers_right = collections.Counter()
        num_bouquets = 0
        for day in sorted(flowers.keys()):
            for idx in flowers[day]:
                start = idx - num_flowers_left[idx - 1]
                num_bouquets -= num_flowers_left[idx - 1] // k
                end = idx + num_flowers_right[idx + 1]
                num_bouquets -= num_flowers_right[idx + 1] // k
                total_num_flowers = end - start + 1
                num_bouquets += total_num_flowers // k
                num_flowers_left[end] = total_num_flowers
                num_flowers_right[start] = total_num_flowers
                if num_bouquets >= m:
                    return day
        return -1
                    
                    


class Solution:
    def minDays(self, A, m, k):
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def bouqets(d):
            res, c = 0, 0
            for n in bloomDay:
                c = 0 if n > d else c + 1
                if c == k:
                    res, c = res + 1, 0
            return res
            
        days = sorted(set(bloomDay))
        lo, hi = 0, len(days)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if bouqets(days[mid]) < m:
                lo = mid + 1
            else:
                hi = mid
        return days[hi] if days[hi] >= m else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if not bloomDay or m*k>len(bloomDay):
            return(-1)
        def feasible(days):
                bouquets,flower=0,0
                for bloom in bloomDay:
                    if bloom>days:
                        flower=0
                    else:
                        bouquets+=(flower+1)//k
                        flower=(flower+1)%k
                return bouquets>=m
        l,r=0,max(bloomDay)
        while(l<r):
            mid=l+(r-l)//2
            if(feasible(mid)):
                r=mid
            else:
                l=mid+1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if m * k > len(bloomDay): return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in bloomDay:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        ## Function to check required bouquets can be made 
        ## within the parameterized number of days.
        def canMakeBouquet(m, k, bloomDay, currDay):
            
            ## Variable for keeping track of 
            ## the number of bouquets made.
            numBouquets = 0
            
            ## Variable for sliding window length.
            slidingWindowLen = 0
            
            for i in range(0, len(bloomDay)):
                
                ## Check whether the flower has bloomed or not.
                if (bloomDay[i] <= currDay):
                    slidingWindowLen += 1
                else:
                    slidingWindowLen = 0
                    
                ## Check whether a bouquet can be constructed.
                if (slidingWindowLen == k):
                    numBouquets += 1
                    slidingWindowLen = 0
                    
            ## Check whether sufficient bouquets can be made.
            return (numBouquets >= m)
        
        ## return canMakeBouquet(m, k, bloomDay, 4)
        
        ## Initialise binary search bounds.
        lowBound = 1
        highBound = max(bloomDay)
        
        ## Perform Binary Search.
        while (lowBound < highBound):
            
            ## Compute the midBound.
            midBound = lowBound + (highBound - lowBound)//2
            
            ## If bouquets cannot be made.
            if (not canMakeBouquet(m, k, bloomDay, midBound)):
                lowBound = midBound + 1
            else:
                highBound = midBound
                
        ## Perform sanity check.
        if (canMakeBouquet(m, k, bloomDay, lowBound)):
            return lowBound
        else:
            return -1
            


class Solution:
    def minDays(self, bloomDay, m: int, k: int) -> int:
        beg = min(bloomDay)
        end = max(bloomDay)
        n = len(bloomDay)
        res = -1
        while (beg <= end):
            mid = beg + int((end - beg) / 2)
            #print(mid)
            if (self.isValid(bloomDay, n, m, k, mid) >= m):
                res = mid
                end = mid - 1
            else:
                beg = mid + 1
        return res

    def isValid(self, bloomDay, n, m, k, mx):
        sum = 0
        boquet = 0
        k1 = 0
        for i in range(n):
            k1 += 1
            if (bloomDay[i] > mx):
                k1 = 0
            if(k1==k):
                boquet+=1
                k1=0
        #print(\"boquet\",boquet)
        return boquet

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m*k: return -1
        
        
        
        
#         def helper(D_days):
#             n_m = 0
#             low = 0 
#             while low + k <= len(bloomDay):
#                 _range = bloomDay[low: low+k]
#                 isValid = True
#                 for fl in _range:
#                     if fl > D_days: 
#                         low += 1
#                         isValid = False
#                         break
#                 if isValid:
#                     n_m += 1
#                     low += k
                
#             if n_m < m: return +1
#             else: return -1
            
        def helper(D_days):
            n_m = 0
            n_k = 0

            for index, fl in enumerate(bloomDay):
                if fl > D_days:
                    n_k = 0
                else: 
                    n_k += 1

                if n_k == k: 
                    n_m +=1 
                    n_k = 0

            if n_m < m: return +1
            else: return -1

                        
            
#             low = 0 
#             while low + k <= len(bloomDay):
#                 _range = bloomDay[low: low+k]
#                 isValid = True
#                 for fl in _range:
#                     if fl > D_days: 
#                         low += 1
#                         isValid = False
#                         break
#                 if isValid:
#                     n_m += 1
#                     low += k
                
#             if n_m < m: return +1
#             else: return -1
    
            
    
                        
# Binary search   
        def B_search():
            low, high = 0, max(bloomDay)+1
            
            while low < high:
                mid = low + (high-low)//2
                
                if helper(mid)==+1:
                    low = mid +1
                else:
                    high = mid
                    
            return low
        
        return B_search()
                    


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low = float('inf')
        high = float('-inf')
        for day in bloomDay:
            low = min(low, day)
            high = max(high, day)
        
        good = set()
        
        i = 0
        while low < high:
            guess = (low + high) >> 1
            
            count = 0
            boquets = 0
            for day in bloomDay:
                if day <= guess:
                    count += 1
                    if count == k:
                        boquets += 1
                        count = 0
                        if boquets == m:
                            break
                else:
                    count = 0
                day += 1
            
            if boquets < m:
                low = guess + 1
            else:
                good.add(guess)
                high = guess
        else:
            if not good:
                count = 0
                boquets = 0
                for day in bloomDay:
                    if day <= high:
                        count += 1
                        if count == k:
                            boquets += 1
                            count = 0
                            if boquets == m:
                                return high
                    else:
                        count = 0
                    day += 1
        
        return min(good) if good else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def canMakeMBouquetsInKDays(max_days):
            flowers = 0
            bouquets = 0
            for flower in range(len(bloomDay)):
                if bloomDay[flower]<=max_days:
                    flowers+=1
                else:
                    flowers=0  
                if flowers==k:
                    bouquets+=1
                    flowers=0
            return bouquets>=m
            
        
        if m*k>len(bloomDay):
            return -1
        
        start = 1
        end = max(bloomDay)
        while start<=end:
            mid = (start+end)//2
            if canMakeMBouquetsInKDays(mid):
                end = mid-1
            else:
                start = mid+1
        return start

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def possible(bloomDay, days, m, k):
            bouq = 0
            curr = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] <= days:
                    curr += 1
                else:
                    curr = 0
                if curr == k:
                    bouq += 1
                    curr = 0
            return bouq >= m
        l = 0
        r = max(bloomDay)
        while l < r:
            mid = (l + r) // 2
            print(mid)
            if possible(bloomDay, mid, m, k):
                r = mid
            else:
                l = mid + 1
        # print(l, possible(bloomDay, l, m, k))
        if possible(bloomDay, l, m, k):
            return l
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def possible(days):
            flowers = 0
            bouquets = 0
            for bloom in bloomDay:
                if bloom<=days:
                    flowers += 1
                    if flowers>=k:
                        bouquets += 1
                        flowers = 0
                        if bouquets>=m:
                            return True
                else:
                    flowers = 0
            return False
            
        if len(bloomDay)<m*k:
            return -1
        
        l = 1
        h = max(bloomDay)
        while l<h:
            days = (l+h)//2
            if possible(days):
                h = days
            else:
                l = days+1
        return l


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self, root = None):
        self.root = root
    
    def insert(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self._insert(self.root, value)
        
        
    def _insert(self, root, v):
        if v < root.val:
            if not root.left:
                root.left = Node(v)
            else:
                self._insert(root.left, v)
        else:
            if not root.right:
                root.right = Node(v)
            else:
                self._insert(root.right, v)
            
    
    def findBounds(self, value, lower, upper):
        root = self.root
        while root:
            if root.val < value:
                lower = root.val
                root = root.right
            else:
                upper = root.val
                root = root.left
        
        return (lower, upper)
                
        
                
                
              
            
                

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        n = len(bloomDay)
        if m*k > n: return -1
        
        h = [(-d,f) for f,d in enumerate(bloomDay)]
        heapq.heapify(h)        
        
        bst = BST()
        fit = n//k
        while True:
            day, flower = heapq.heappop(h)
            l, u = bst.findBounds(flower, -1, n)
            fit +=  (flower-l-1)//k + (u-flower-1)//k - (u-l-1)//k
            bst.insert(flower)
            if fit < m:
                return -day
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        min_day, max_day = min(bloomDay), max(bloomDay)
        
        while min_day < max_day:
            mid = min_day + (max_day - min_day) // 2
            if self.check(bloomDay, mid, m , k):
                max_day = mid
            else:
                min_day = mid + 1
        return min_day
    
    
    def check(self, bloomDay, day, m, k):
        un_m = 0
        last_bloom = -1 
        n_before_bloom = 0
        for i, d in enumerate(bloomDay):
            if d <= day:
                n_before_bloom += 1
                last_bloom = i
                if n_before_bloom >= k:
                    un_m += 1
                    n_before_bloom -= k
            else:
                n_before_bloom = 0
        return un_m >= m
                        
                        
                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMakeBouquets(cap):
            nBouquets = 0
            nFlowers = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] > cap:
                    nFlowers = 0
                    continue
                nFlowers += 1
                if nFlowers == k:
                    nBouquets += 1
                    nFlowers = 0
            return nBouquets >= m
        
        if m*k > len(bloomDay):
            return -1
        
        lo, hi = 1, max(bloomDay)
        while lo < hi:
            med = lo + (hi-lo)//2
            if canMakeBouquets(med):
                hi = med
            else:
                lo = med + 1
        return hi

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        mi,ma = min(bloomDay),max(bloomDay)
        while(mi<ma):
            mid = (mi + ma)//2
            curr=0
            adj=0
            for i in range(len(bloomDay)):
                if bloomDay[i]>mid:
                    adj=0
                else:
                    adj+=1
                    if adj==k:
                        adj=0
                        curr+=1
                if curr>=m:
                    break
            if curr<m:
                mi = mid+1
            else:
                ma = mid
        return (mi)       


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if k * m > len(bloomDay):
            return -1
        
        def flowers(days):
            boq, full = 0, 0
            adj = False
            for flower in bloomDay:
                if flower <= days:
                    full += 1
                else:
                    full = 0
                if full == k:
                    full = 0
                    boq += 1
            return boq >= m
             
        left, right = 0, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if flowers(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            bouquets=flowers=0
            for i in range(len(bloomDay)):
                if bloomDay[i]<=days:
                    flowers+=1
                    if flowers==k:
                        bouquets+=1
                        flowers=0
                    if bouquets>=m:
                        return True
                else:
                    flowers=0
            return False
        if m*k>len(bloomDay):
            return -1
        left,right=min(bloomDay),max(bloomDay)
        while left<right:
            mid=left+(right-left)//2
            if feasible(mid):
                right=mid
            else:
                left=mid+1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = max(bloomDay)
        if m*k > len(bloomDay):
            return -1
        
        l, r = 1, n
        while l <= r:
            mid = (l+r)//2
            count, rec = 0, 0
            
            for i in range(len(bloomDay)):
                if bloomDay[i] <= mid:
                    count += 1
                    if count >= k:
                        rec += 1
                        count = 0
                    if rec >= m:
                        break
                else:
                    count = 0
            
            if rec < m: #need more bouquets, increase the mid makes it easy to collect flowers
                l = mid+1
            else:
                r = mid-1
        
        return l


class Solution:
    def minDays(self, b: List[int], m: int, k: int) -> int:
        mi,ma=min(b),max(b)
        if m*k>len(b):
            return -1
        n=len(b)
        cur,adj=0,0
        while(mi<ma):
            mid=(mi+ma)//2
            cur,adj=0,0
            for i in range(n):
                if(mid<b[i]):
                    adj=0
                else:
                    adj+=1
                    if(adj==k):
                        cur+=1
                        adj=0
                if(cur>=m):
                    break
            if(cur<m):
                mi=mid+1
            else:
                ma=mid
        return mi

from collections import Counter
from heapq import *
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if k*m > len(bloomDay): return -1
        
        que = [[-1*num,ind] for ind,num in enumerate(bloomDay[:k])]
        heapify(que)
        
        maxArr = [-1*que[0][0]]
        for ind in range(k,len(bloomDay)):
            while que and que[0][1] <= ind-k:
                heappop(que)
            heappush(que, [-1*bloomDay[ind], ind])
            maxArr.append(-1*que[0][0])
            
        # print(maxArr)
        def isValid(num):
            cnt = 0
            ind = 0
            while ind < len(maxArr):
                if maxArr[ind] <= num:
                    cnt+=1
                    ind+=k
                else:
                    ind+=1
            # print(\"{0} => {1}\".format(num, cnt))
            return cnt >= m
                
        
        low = 1
        high = max(bloomDay)+1
        ans = -1
        while low < high:
            mid = low + (high-low)//2
            if isValid(mid):
                high = mid
                ans = mid
            else:
                low=mid+1
        return ans
            
            
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) // k < m:
            return -1
        low, high = min(bloomDay), max(bloomDay)
        
        def valid(days):
            start = 0
            count = 0
            for i, val in enumerate(bloomDay):
                if val <= days:
                    if i - start + 1 >= k:
                        count += 1
                        start = i + 1
                else:
                    start = i + 1
            
            return count >= m

        while low < high:
            days = (low + high) // 2
            
            if valid(days):
                high = days
            else:
                low = days + 1
        
        return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

        if m*k>len(bloomDay):
            return -1


        def check(days):

            i = 0
            bouquet = 0
            count = 0
            for i in range(len(bloomDay)):
                if bloomDay[i]<=days:
                    count+=1
                else:
                    count = 0

                if count == k:
                    bouquet+=1
                    count = 0
                if bouquet == m:
                    return True
            return False

        low,high = min(bloomDay),max(bloomDay)

        while low<high:

            mid = low + (high-low)//2

            possible = check(mid)

            if possible:
                high = mid
            else:
                low = mid+1

        return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if k*m > n:
            return -1
        l, r = 1, max(bloomDay)
        ans = -1
        while l <= r:
            mid = int((l+r)/2)
            bouquetCount = 0
            adjacentFlowerCount = 0
            for bloom in bloomDay:
                if bloom <= mid:
                    adjacentFlowerCount += 1
                    if adjacentFlowerCount == k:
                        bouquetCount += 1
                        adjacentFlowerCount = 0
                        if bouquetCount == m:
                            break
                else:
                    adjacentFlowerCount = 0
            if bouquetCount == m:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1
        lo = min(bloomDay)
        hi = max(bloomDay)
        while lo < hi:
            mid = lo + (hi-lo)//2
            pos_b = 0
            cur_b = 0
            for f in bloomDay:
                if f <= mid:
                    cur_b += 1
                else:
                    cur_b = 0
                if cur_b == k:
                    pos_b += 1
                    cur_b = 0
            if pos_b >= m:
                hi = mid
            else:
                lo = mid+1
        return lo

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def feasible(day):
            
            bou = 0
            flowers = 0
            
            for bloom in bloomDay:
                if bloom > day:
                    flowers = 0
                else:
                    bou += (flowers+1)//k
                    flowers = (flowers+1)%k
            
            
            if bou < m:
                return False
            return True
        
        if len(bloomDay) < (m*k):
            return -1
        
        left = 1
        right = max(bloomDay)
        
        while left < right :
            mid = (left+right)//2
            
            if feasible(mid):
                right = mid
            else: left = mid + 1
                
        return left

class Solution:
    def minDays(self, B: List[int], m: int, k: int) -> int:
        
        n = len(B)
        if m*k>n: return -1
        
        lo = min(B)
        hi = max(B)+1
        while lo<hi:
            mi = lo+(hi-lo)//2
            bouquets = 0
            curflowers = 0
            for i in range(n):
                if B[i]<=mi:
                    curflowers += 1
                else:
                    curflowers = 0
                    
                if curflowers == k:
                    bouquets += 1
                    curflowers = 0
                #print(m,i,curflowers,bouquets)
                    
                if bouquets == m:
                    #print(m,i,'here')
                    hi = mi
                    break
            if hi>mi:
                lo = mi+1
            
        return lo

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def make_boquets(mid):
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > mid:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m
        left,right = min(bloomDay), max(bloomDay) + 1
        while left < right:
            mid = left + (right-left)//2
            if make_boquets(mid):
                right = mid
            else:
                left = mid + 1
        if left > max(bloomDay):
            return -1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = max(bloomDay)
        if m*k > len(bloomDay):
            return -1
        
        l, r = 1, n
        while l <= r:
            mid = (l+r)//2 #need a threshold for collecting, binary search this threshold
            count, rec = 0, 0
            
            for i in range(len(bloomDay)):
                if bloomDay[i] <= mid:
                    count += 1
                    if count >= k:
                        rec += 1
                        count = 0
                    if rec >= m:
                        break
                else:
                    count = 0
            
            if rec < m: #need more bouquets, increase the mid makes it easy to collect flowers
                l = mid+1
            else:
                r = mid-1
        
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def feasible(days):
            flower = 0
            bouq = 0
            #print('----------'+str(days))
            for bloom in bloomDay:
                if bloom > days:
                    flower = 0
                else:
                    flower += 1
                    #print(bloom,flower)
                    if flower >= k:
                        bouq += 1
                        flower = 0
                        #print(bloom,bouq)
            return bouq >= m
        
        left = 1
        right = max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            flower = 0
            boq = 0
            for bloom in bloomDay:
                if bloom > days:
                    flower = 0
                    
                else:
                    boq = boq + (flower+1)//k
                    flower = (flower+ 1)%k
                    
            if boq >= m:
                return True
            
            return False
            
        if len(bloomDay) < m * k:
            return -1
    
        low = min(bloomDay)
        high = max(bloomDay)
        
        
        while low < high:
            mid = (low+high)//2
            if feasible(mid):
                high = mid
                
            else:
                low = mid + 1
                
        return low
    


    # if len(bloomDay) < m * k:
    #     return -1
    # left, right = 1, max(bloomDay)
    # while left < right:
    #     mid = left + (right - left) // 2
    #     if feasible(mid):
    #         right = mid
    #     else:
    #         left = mid + 1
    # return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def canMakeMBouquetsInKDays(max_days):
            flowers = 0
            bouquets = 0
            for flower in range(len(bloomDay)):
                if bloomDay[flower]<=max_days:
                    flowers+=1
                else:
                    flowers=0  
                if flowers==k:
                    bouquets+=1
                    flowers=0
                if bouquets==m:
                    return True
            return bouquets>=m
            
        
        if m*k>len(bloomDay):
            return -1
        
        start = 1
        end = max(bloomDay)
        while start<=end:
            mid = (start+end)//2
            if canMakeMBouquetsInKDays(mid):
                end = mid-1
            else:
                start = mid+1
        return start

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        def check(curr_day):
            ans = 0
            i = -1
            for j, day in enumerate(bloomDay):
                if day > curr_day:
                    ans += (j - 1 - i) // k
                    i = j
                if ans >= m:
                    return True
            ans += (len(bloomDay) - 1 - i) // k
            return ans >= m
        candidates = sorted(set(bloomDay))
        
        l, r = 0, len(candidates) - 1
        while r > l:
            mid = l + (r - l) // 2
            if check(candidates[mid]):
                r = mid
            else:
                l = mid + 1
        return candidates[l]


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        eV = max(bloomDay)
        sV = min(bloomDay)
        
        while sV <= eV:
            mV = (sV+eV) // 2
            i = 0
            x = 0
            c = 0
            while i < n:
                if bloomDay[i] <= mV:
                    x += 1
                    if x >= k:
                        c += 1
                        if c >= m:
                            break
                        x = 0
                else:
                    x = 0
                i += 1
            else:
                sV = mV + 1
                continue
            eV = mV - 1
        
        return sV
                
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(day):
            numAdjFlowers = 0
            numBouquets = 0
            
            for bloom in bloomDay:
                if bloom <= day:
                    numAdjFlowers += 1
                    if numAdjFlowers == k:
                        numBouquets += 1
                        numAdjFlowers = 0
                else:
                    numAdjFlowers = 0
            return numBouquets >= m
                    
        # Eliminate cases where it's not possible
        if len(bloomDay) < (m*k):
            return -1
                    
        left = min(bloomDay)
        right = max(bloomDay)
        
        while left < right:
            mid = left + (right - left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self,bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        if len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left
    


class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.size = [1 for _ in range(n)]
        
    def find(self, x):
        if self.father[x] != x:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        self.father[fx] = fy
        self.size[fy] += self.size[fx]
        
    def get_size(self, x):
        fx = self.find(x)
        return self.size[fx]

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        sort_indexes = sorted(range(n), key = lambda i: bloomDay[i])
        uf = UnionFind(n)
        bouquets = 0
        bloomed = [False] * n
        for idx in sort_indexes:
            bloomed[idx] = True
            left, right = idx - 1, idx + 1
            left_size, right_size = 0, 0
            if left >= 0 and bloomed[left]:
                left_size = uf.get_size(left)
                uf.union(left, idx)
            if right <= n - 1 and bloomed[right]:
                right_size = uf.get_size(right)
                uf.union(right, idx)
            cur_size = uf.get_size(idx)
            bouquets += cur_size // k - (left_size // k + right_size // k)
            # print(bouquets, bloomed, left_size, right_size, cur_size)
            if bouquets >= m:
                return bloomDay[idx]
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        min_day, max_day = min(bloomDay), max(bloomDay)
        
        while min_day <= max_day:
            mid = min_day + (max_day - min_day) // 2
            if self.check(bloomDay, mid, m , k):
                if max_day == mid:
                    return max_day
                max_day = mid
            else:
                min_day = mid + 1
        return max_day
    
    
    def check(self, bloomDay, day, m, k):
        un_m = 0
        last_bloom = -1 
        n_before_bloom = 0
        for i, d in enumerate(bloomDay):
            if d <= day:
                n_before_bloom += 1
                last_bloom = i
                if n_before_bloom >= k:
                    un_m += 1
                    n_before_bloom -= k
            else:
                n_before_bloom = 0
        return un_m >= m
                        
                        
                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def feasible_bloom_day(value):
            total_bouquet = 0
            num_flowers = 0
            
            for bloom in bloomDay:
                # Flower bloomed
                if ((bloom-1) // value) == 0:
                    num_flowers += 1
                
                    if num_flowers == k:
                        total_bouquet += 1
                        num_flowers = 0
                        
                    if total_bouquet == m:
                        return True
                else: 
                    num_flowers = 0
                    
            
            return False
        
        left, right = 1, max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if feasible_bloom_day(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def make_bouquets(mid):
            bouquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > mid:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m
        left,right = min(bloomDay), max(bloomDay) + 1
        while left < right:
            mid = left + (right-left)//2
            if make_bouquets(mid):
                right = mid
            else:
                left = mid + 1
        if left > max(bloomDay):
            return -1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        if len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        if len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left
    
#     def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
#         def feasible(day):
#             adj_count = 0
#             bouquet = 0
#             for bday in bloomDay:
#                 if bday <= day:
#                     adj_count += 1
#                 else:
#                     adj_count = 0
#                 if adj_count == k:
#                     bouquet += 1
#                     adj_count = 0
#             return bouquet == m
        
#         if len(bloomDay) < m * k:
#             return -1
#         left, right = 1, max(bloomDay)
#         while left < right:
#             mid = (left + right) // 2
#             if feasible(mid):
#                 right = mid
#             else:
#                 left = mid + 1
#         return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        groups = dict()
        sorted_original_idx_and_days = sorted(enumerate(bloomDay), key=lambda item: item[1])
        
        SIZE = len(sorted_original_idx_and_days)
        bloom_flag = [False]*SIZE
        max_right = [-1]*SIZE
        min_left = [-1]*SIZE
        count = 0
        
        merge_right_flag = False
        merge_left_flag = False
        for idx, (ith_flower, day) in enumerate(sorted_original_idx_and_days):
            # print(\"=\"*50)
            bloom_flag[ith_flower] = True
            max_right[ith_flower] = min_left[ith_flower] = ith_flower
            merge_left_flag = merge_right_flag = False
            if ith_flower < SIZE-1 and bloom_flag[ith_flower+1]:
                merge_right_flag = True
                ptr = ith_flower+1
                while max_right[ptr] != -1 and max_right[ptr] != ptr:
                    ptr = max_right[ptr]
                max_right[ith_flower] = ptr
            if ith_flower > 0 and bloom_flag[ith_flower-1]:
                merge_left_flag = True
                ptr = ith_flower-1
                while min_left[ptr] != -1 and min_left[ptr] != ptr:
                    ptr = min_left[ptr]
                min_left[ith_flower] = ptr
            max_right[min_left[ith_flower]] = max_right[ith_flower]
            min_left[max_right[ith_flower]] = min_left[ith_flower]
            
            if merge_left_flag:
                # print(\"merge left\", (ith_flower-min_left[ith_flower])//k)
                count -= (ith_flower-min_left[ith_flower])//k
            if merge_right_flag:
                # print(\"merge right\", ((max_right[ith_flower]+1)-ith_flower)//k)
                count -= (max_right[ith_flower]-ith_flower)//k
            count += ((max_right[ith_flower]+1)-min_left[ith_flower])//k
            
            # print(bloom_flag)
            # print(max_right)
            # print(min_left)
            # print(count)
            if count >= m:
                return day
        return -1

class Solution:
    def calc(self, bloomDay, mid, k):
        adj=0
        totes=0
        for i in range(len(bloomDay)):
            if adj==k:
                totes+=1
                adj=0
            if bloomDay[i]<=mid:
                adj+=1
                continue
            adj=0
        if adj==k:
            totes+=1
        return totes
                
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n=len(bloomDay)
        if m*k>n:
            return -1
        
        l=0
        r=max(bloomDay)+1
        while r-l>1:
            mid=l + (r-l)//2
            t=self.calc(bloomDay, mid, k)
            if t>=m:
                r=mid
            elif t<m:
                l=mid
        
        return r
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            cur = 0
            bou = 0
            for b in bloomDay:
                if b <= days:
                    cur += 1
                    if cur == k:
                        bou += 1
                        if bou >= m:
                            return True
                        cur = 0
                else:
                    cur = 0
            return False
            
        
        if m * k > len(bloomDay):
            return -1
        if m * k == len(bloomDay):
            return max(bloomDay)
        
        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            mid = l + (r - l) // 2
            if feasible(mid):
                r = mid
            else:
                l = mid + 1
        
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
    
        def condition(cap):
            curr_m = 0
            curr_k = 0
            for flower in bloomDay:
                if flower <= cap: # 1 # 10 # 3 # 10 # 2
                    curr_k += 1 # 1 # 1 # 1
                    if curr_k == k:
                        curr_m += 1 # 1 # 2 # 3
                        curr_k = 0 # 0 # 0
                    if curr_m >= m: # F # F
                        return True
                else:
                    curr_k = 0  # 0 # 0
            return False
                        
                
        
        left, right = 1, max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n=len(bloomDay)
        if m*k>n: return -1
        
        def canmake(days):
            flowers=0
            bs=0
            i=0
            while bs<m and i<n:
                while flowers<k and i<n:
                    if bloomDay[i]<=days:
                        flowers+=1
                    else:
                        flowers=0
                    i+=1
                if flowers==k:
                    flowers=0
                    bs+=1
            return bs==m
        
        l,r=min(bloomDay),max(bloomDay)
        
        while l<r:
            mid=(l+r)>>1
            if canmake(mid):
                r=mid
            else:
                l=mid+1
        return l

class Solution:
    def minDays(self, bloomDay, m, k):
        
        if m * k > len(bloomDay): return -1
            
        def canBloom(cand):
            bloomed = 0
            bouquet = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] > cand:
                    bouquet = 0
                else:
                    bouquet += 1
                    if bouquet == k:
                        bloomed += 1
                        bouquet = 0
            return bloomed>=m

        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            mid = l + (r - l) // 2
            if canBloom(mid):
                r = mid
            else:
                l = mid + 1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        left, right = 1, max(bloomDay)
        while left<right:
            mid = (left+right)//2
            flower, bouquet = 0, 0
            for b in bloomDay:
                flower = 0 if b>mid else flower + 1
                if flower>=k:
                    flower = 0
                    bouquet += 1
                    if bouquet==m: break
            if bouquet == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        
        def feasible(threshold):
            bouquets = 0
            flowers = 0
            
            for bloom in bloomDay:
                if bloom > threshold:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m
            
        if m*k > n:
            return -1
        
        left, right = 1, max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            bouquets,flowers=0,0
            for bloom in bloomDay:
                if bloom>days:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
        
        
        if len(bloomDay)<m*k:
            return -1
        l,r=1,max(bloomDay)
        while l<r:
            mid=(l+r)//2
            if feasible(mid):
                r=mid
            else:
                l=mid+1
        return l

class Solution:
    def minDays(self, bd: List[int], m: int, k: int) -> int:
        if m * k > len(bd): return -1
        
        def helper(d):
            ans, cur = 0, 0
            for b in bd:
                cur = 0 if b > d else cur+1
                if cur == k:
                    ans += 1
                    cur = 0
            return ans
        
        days = sorted(set(bd))
        l, h = 0, len(days) - 1
        while l<h:
            mid = (l+h)//2
            if helper(days[mid]) < m:
                l = mid + 1
            else:
                h = mid
        
        return days[h] if helper(days[h])>=m else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMakeBouquets(blooms:List[bool], m:int, k:int)->bool:
            bouqs_to_fit = m
            run = 0
            for f in blooms:
                if f:
                    run +=1
                else:
                    run = 0
                if run == k:
                    bouqs_to_fit -=1 #fit a bouquet
                    run = 0
            return bouqs_to_fit <= 0
        if len(bloomDay) < m*k:
            return -1
        
        candidates = sorted(set(bloomDay))
        
        lo = 0
        hi = len(candidates)-1
        while(lo < hi):
            mid = (lo + hi)//2
            if canMakeBouquets(map(lambda x: x<=candidates[mid], bloomDay),m,k):
                hi = mid
            else:
                lo = mid + 1
        return candidates[lo]

from functools import reduce
class Solution:
    def valid(self, bloomDay, k, m, mid):
        i, n = 0, len(bloomDay)
        while i+k-1 < n:
            j = i
            while j < n and j < i+k:
                if bloomDay[j] > mid:
                    i = j+1
                    break
                j+=1
            else:
                m-=1
                i = j
            if m <= 0:
                return True
        return False
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if (len(bloomDay) < m*k): return -1
        l, r = reduce(lambda a, b: (min(a[0], b), max(a[1], b)), bloomDay, (float('inf'), float('-inf')))
        while l < r:
            mid = (l+r-1)//2
            v = self.valid(bloomDay, k, m, mid)
            if v:
                r = mid
            else:
                l = mid+1
        return r

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # This is a greedy approach and is generally O(N) time
        def is_feasible(max_day) -> bool:
            total_bouquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > max_day:
                    flowers = 0
                else:
                    total_bouquets += (flowers + 1)//k
                    flowers = (flowers + 1) % k
            return total_bouquets >= m
                    
        if m * k > len(bloomDay):
            return -1
        
        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            mid = l + (r - l)//2
            if is_feasible(mid):
                r = mid
            else:
                l = mid + 1
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        
        def feasible(day):
            flowers,bouquets=0,0
            for bloom in bloomDay:
                if bloom>day:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
            
        
        l,r=1,max(bloomDay)
        while l<r:
            mid=(l+r)//2
            if feasible(mid):
                r=mid
            else:
                l=mid+1
        return l
    


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        
        def enough(Day):
            flowers,bouquets=0,0
            for bloom in bloomDay:
                if bloom>Day:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
        
        l,r=1,max(bloomDay)
        while l<r:
            mid=(l+r)//2
            if enough(mid):
                r=mid
            else:
                l=mid+1
        return l

import heapq

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay): return -1
        
        def is_valid(mid):
            count, size = 0, 0
            
            for i, v in enumerate(bloomDay):
                size = size+1 if v <= mid else 0
                # print(f\"\\tsize: {size} count: {count} i: {i} v: {v}\")
                
                if size == k:
                    size = 0
                    count += 1
                if count == m:
                    return True
                
            return False
        
        left, right = float('inf'), float('-inf')
        for i, v in enumerate(bloomDay):
            left = min(left, v)
            right = max(right, v)
        # print(f\"left: {left}, right: {right}\")
            
        while left <= right:
            mid =  left + (right - left) // 2
            # print(left, right, mid)
            
            if is_valid(mid):
                right = mid - 1
            else:
                left = mid + 1
                
        return left if left != float('-inf') else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            bouquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bouquets += (flowers + 1)//k
                    flowers = (flowers+1)%k
            return bouquets >= m
        
        if m*k > len(bloomDay):
            return -1
        lo, hi = 1, max(bloomDay)
        
        while lo < hi:
            mid = lo + (hi-lo)//2
            if feasible(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo


class Solution:
    def minDays(self, A, m, k):
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) / 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return int(left)


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if self.validBouquets(bloomDay, mid, m, k):
                right = mid
            else:
                left = mid + 1
        return left
    
    def validBouquets(self, bloomDay, days, m, k):
        # Count how many bouquets we can collect
        count_bouquets = 0
        temp_flowers = 0
        for bloom in bloomDay:
            if bloom <= days:
                temp_flowers += 1
            else:
                temp_flowers = 0
            # Determine whether flowers in hand can form a bouquet
            if temp_flowers >= k:
                count_bouquets += 1
                temp_flowers = 0
                if count_bouquets == m:
                    return True
        return False

class Solution:
    def search(self, bloomDay, m, k, days):
        bouquets = 0
        flowers = 0
        for day in bloomDay:
            if day > days:
                flowers = 0
            else:
                bouquets += (flowers + 1) // k
                flowers = (flowers + 1) % k
               
        return bouquets >= m
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        lowerBound = 1
        upperBound = max(bloomDay)
        
        while lowerBound <= upperBound:
            mid = (lowerBound + upperBound) // 2
            check = self.search(bloomDay, m, k, mid)
            if check:
                upperBound = mid - 1
            else:
                lowerBound = mid + 1
        return lowerBound

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(day) -> bool:
            a = 0
            b = 0
            for bloom in bloomDay:
                if bloom <= day:
                    a += 1
                else:
                    b += a//k
                    a = 0
            b += a//k
            return b >= m
        
        if len(bloomDay) < m * k:
            return -1
        
        left, right = 1, max(bloomDay) # could be [0, n], [1, n] etc. Depends on problem
        while left < right:
            mid = (left + right) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if len(bloomDay)<m*k:
            return -1
        def feasible(days):
            flowers,bouquets=0,0
            for bloom in bloomDay:
                if bloom>days:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
        
        l,r=1,max(bloomDay)
        while l<r:
            mid=(l+r)//2
            if feasible(mid):
                r=mid
            else:
                l=mid+1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        
        def feasible(Day):
            flowers,bouquets=0,0
            for bloom in bloomDay:
                if bloom>Day:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
        
        l,r=1,max(bloomDay)
        while l<r:
            mid=(l+r)//2
            if feasible(mid):
                r=mid
            else:
                l=mid+1
        return l

from typing import List


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(numDays: int) -> bool:
            flowers, bouquets = 0, 0
            for bloom in bloomDay:
                if numDays < bloom:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m

        if len(bloomDay) < m * k: return -1
        low, high = min(bloomDay), max(bloomDay)
        while low < high:
            mid = low + (high - low) // 2
            if condition(mid):
                high = mid
            else:
                low = mid + 1
        return low




class Solution:
    def minDays(self, bloomDay: List[int], n: int, k: int) -> int:
        def ok(m, n):
            bloomed = [d <= m for d in bloomDay]
            c = i = j = 0
            while i < len(bloomed)-k+1:
                for _ in range(k):
                    if bloomed[j]:
                        j += 1
                    else:
                        i = j = j+1
                        break
                else:
                    i = j
                    c += 1
                    if c == n:
                        break
            else:
                return False
            return True
        
        
        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            m = (l+r) // 2
            if ok(m, n):
                r = m
            else:
                l = m+1
        return l if ok(l, n) else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m*k:
            return -1
        left, right = min(bloomDay), max(bloomDay)
        def condition(day):
            counter = 0
            res = 0
            for d in bloomDay:
                if d<=day:
                    counter += 1
                else:
                    counter = 0
                if counter >=k:
                    res += 1
                    counter = 0
            return res >= m
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            bouquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m
        
        if len(bloomDay) < (m * k):
            return -1
            
        l, r = 1, max(bloomDay)
        while l < r:
            mid = (l + r) // 2
            if feasible(mid):
                r = mid
            else:
                l = mid + 1
        return l

class Solution:
    def minDays(self, bloom: List[int], m: int, k: int) -> int:
        def isFeasible(day):
            flower,bouqets=0,0
            for b in bloom:
                if b>day:
                    flower=0
                else:
                    bouqets+=(flower+1)//k
                    flower=(flower+1)%k
            return bouqets>=m
        
        if len(bloom) < m * k:
            return -1
        l,r=1,max(bloom)
        while l<r:
            mid=l+(r-l)//2
            if isFeasible(mid):
                r=mid
            else:
                l=mid+1
                
        return l
            
            
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(x):
            count = 0
            M = 0
            for i, day in enumerate(bloomDay):
                bloom = 0
                if day <= x:
                    bloom = 1
                    count += 1
                    if count >= k:
                        count = 0
                        M += 1
                    if M >= m:
                        return True
                else:
                    count = 0
            return False

        if len(bloomDay) < m*k: return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMake(bloomDay, m, k, day):
            
            r, cur, cnt = 0, 0, 0
            while r < len(bloomDay):
                if bloomDay[r] <= day:
                    cur += 1
                    if cur == k:
                        cnt += 1
                        cur = 0
                        if cnt == m:
                            return True
                else:
                    cur = 0
                r += 1
            return False
        if m*k > len(bloomDay):
            return -1
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if not canMake(bloomDay, m, k, mid):
                left = mid + 1
            else:
                right = mid
        return left


# check length of array with total number of flowers needed- 
#https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/discuss/691031/Python3-Binary-Search-(ELIF5%3A-Explained-Like-I'm-5-Years-Old)
class Solution:
    def minDays(self, listOfFlowerBloomDays: List[int], targetNumberOfBouquets: int, flowersPerBouquet: int) -> int:
        def numberOfBouquetsWeCanMakeOnThisDay(dayThatWeAreChecking):
            
            currentListOfAdjacentBloomedFlowers = []
            numberOfBouquetsWeCanMakeOnThisDay = 0
            
            for dayThatFlowerBlooms in listOfFlowerBloomDays: 
                if dayThatFlowerBlooms <= dayThatWeAreChecking:
                    currentListOfAdjacentBloomedFlowers.append('x')   
                else:
                    numberOfBouquetsWeCanMakeOnThisDay += len(currentListOfAdjacentBloomedFlowers)//flowersPerBouquet
                    currentListOfAdjacentBloomedFlowers = []

            numberOfBouquetsWeCanMakeOnThisDay += len(currentListOfAdjacentBloomedFlowers)//flowersPerBouquet
                    
            return numberOfBouquetsWeCanMakeOnThisDay
        
        totalNumberOfFlowersNeeded = targetNumberOfBouquets*flowersPerBouquet
        numberOfFlowersWeCanGrow = len(listOfFlowerBloomDays)
        
        if numberOfFlowersWeCanGrow < totalNumberOfFlowersNeeded: 
            return -1
        
        leftDay = 0
        rightDay = max(listOfFlowerBloomDays)
        
        while leftDay < rightDay:
            
            currentDay = leftDay + (rightDay-leftDay)//2
            if numberOfBouquetsWeCanMakeOnThisDay(currentDay) < targetNumberOfBouquets:
                leftDay = currentDay+1
            else:
                rightDay = currentDay

        return leftDay

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(x):
            count = 0
            M = 0
            for i, day in enumerate(bloomDay):
                bloom = 0
                if day <= x:
                    bloom = 1
                if bloom:
                    count += 1
                else:
                    count = 0
                if count >= k:
                    count = 0
                    M += 1
                if M >= m:
                    return True
            return False

        if len(bloomDay) < m*k: return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # m -- qty of bouquets, k -- qty of flowers
        if len(bloomDay) < m * k:
            return - 1
        def feasible(days):
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m
        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        
        def isFeasible(days):
            
            bouquetsSoFar = 0
            flowersSoFar = 0
            
            for d in bloomDay:
                
                if d <= days:
                    bouquetsSoFar += (flowersSoFar + 1) // k
                    flowersSoFar = (flowersSoFar + 1) % k
                    if bouquetsSoFar == m:
                        return True
                else:
                    flowersSoFar = 0
                
            return False
        
        if len(bloomDay) < m * k:
            return -1
        
        left, right = min(bloomDay), max(bloomDay)
        
        while left < right:
            
            mid = left + (right - left) // 2
            
            if isFeasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    IMPOSSIBLE = -1
    
#     @staticmethod
#     def canMakeBouquetsOnDay(bloom_day: List[int], m: int, k: int, day: int) -> bool:
#         n = len(bloom_day)
#         bouquets_made = 0
#         i = 0
#         while i < n and bouquets_made < m:
#             j = i
#             while j < n and bloom_day[j] <= day:
#                 j += 1
#             if i == j:
#                 i += 1
#             else:
#                 bouquets_made += (j - i) // k
#                 i = j
#         return bouquets_made >= m
    
#     def minDays(self, bloom_day: List[int], m: int, k: int) -> int:
#         n = len(bloom_day)
#         if k * m > n:
#             return Solution.IMPOSSIBLE
#         l = min(bloom_day) - 1
#         r = max(bloom_day)
#         # The invariant is it is possible to make k bouquets on day r.
#         while r - l > 1:
#             middle = (l + r) // 2
#             if Solution.canMakeBouquetsOnDay(bloom_day, m, k, middle):
#                 r = middle
#             else:
#                 l = middle
#         return r

    def bouquetsFrom(self, l: int, r: int) -> int:
        return (r - l + 1) // self.k

    def minDays(self, bloom_day: List[int], m: int, k: int) -> int:
        self.k = k
        n = len(bloom_day)
        if k * m > n:
            return Solution.IMPOSSIBLE
        bloom_order = list(range(n))
        bloom_order.sort(key=lambda index: bloom_day[index])
        bloomed = [False for _ in range(n)]
        to_left = [0 for _ in range(n)]
        to_right = [0 for _ in range(n)]
        bouquets_made = 0
        for index in bloom_order:
            bloomed[index] = True
            l = index
            r = index
            if index != 0 and bloomed[index - 1]:
                bouquets_made -= self.bouquetsFrom(
                    to_left[index - 1], to_right[index - 1])
                l = to_left[index - 1]
            if index + 1 != n and bloomed[index + 1]:
                bouquets_made -= self.bouquetsFrom(
                    to_left[index + 1], to_right[index + 1])
                r = to_right[index + 1]
            bouquets_made += self.bouquetsFrom(l, r)
            to_left[l] = to_left[r] = l
            to_right[l] = to_right[r] = r
            if bouquets_made >= m:
                return bloom_day[index]
        return Solution.IMPOSSIBLE


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A):
            return -1
        
        def isit(d):
            b = m
            for i, j in itertools.groupby(A, key=lambda x: x<=d):
                l = sum(1 for _ in j)
                if i==True:
                    b -= l//k
                if b<=0:
                    break
            return b<=0

        l = 1
        r = max(A)
        while l < r:
            mid = (l+r)//2
            if isit(mid):
                r = mid
            else:
                l = mid + 1
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        '''
        binary search
        '''
        def check(day):
            adjacent = 0
            made = 0
            for f in range(len(flowers)):
                if day >= bloomDay[f]:
                    flowers[f] = True
                    adjacent += 1
                else:
                    adjacent = 0
                if adjacent>=k:
                    adjacent = 0
                    made += 1
                if made >= m:
                    return True
            return False
        
        if len(bloomDay) < m * k:
            return -1
        
        flowers = [False] * len(bloomDay)
        
        l=1
        r=max(bloomDay)
        while l<r:
            mid = l + (r - l)//2
            if check(mid):
                r = mid
            else:
                l = mid+1
        return l
                    
                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l = min(bloomDay)
        r = max(bloomDay)
        ans = -1
        
        while l <= r:
            mid = (l + r) >> 1
            adjs = 0
            bouqs = 0
            for day in bloomDay:
                if day <= mid:
                    adjs += 1
                else:
                    bouqs += adjs // k
                    if bouqs >= m:
                        break
                    adjs = 0
            
            bouqs += adjs // k
            if bouqs >= m:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
            
        return ans

class Solution:
    def checkDate(self, bloom, m, k, day):
        streak = 0
        count = 0 
        for b in bloom:
            if b <= day:
                streak += 1
                if streak == k:
                    count += 1
                    if count == m:
                        return True
                    streak = 0
            else:
                streak = 0
        return False
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left, right = min(bloomDay), max(bloomDay) + 1
        
        while left < right:
            mid = left + (right - left) // 2
            if self.checkDate(bloomDay, m, k, mid):
                right = mid
            else:
                left = mid + 1
                
        return left if left != max(bloomDay) + 1 else -1

class Solution:
    def checkL(self,arr,t,k):
        ans=0
        temp=0
        for i,n in enumerate(arr):
            if t>=n:
                temp+=1
            else:
                ans+=temp//k
                temp=0
        ans+=temp//k
        return ans
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l=min(bloomDay)
        r=max(bloomDay)
        mm = r
        while l<=r:
            mid = (l+r)//2
            if self.checkL(bloomDay,mid,k)>=m:
                r=mid-1
            elif self.checkL(bloomDay,mid,k)<m:
                l=mid+1
        if l==mm+1:
            return -1
        return l    

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def possible(days):
            bonquets = flowers = 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m
        
        if len(bloomDay) < m * k:
            return -1

        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = (left + right) >> 1
            if possible(mid):
                right = mid
            else:
                left = mid + 1
        return left if possible(left) else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(day):
            flowers = list(map(lambda d: d <= day, bloomDay))
            mm = 0
            kk = 0
            for f in flowers:
                if f is False:
                    kk = 0
                else:
                    kk += 1
                    if kk == k:
                        mm += 1
                        kk = 0
            return mm >= m
        days = sorted(list(set(bloomDay)))
        def binarysearch(i, j):
            if j <= i: return -1
            if j - i <= 2:
                for ii in range(i, j):
                    if check(days[ii]): return days[ii]
                return -1
            mid = (i + j) // 2
            if check(days[mid]): return binarysearch(i, mid+1)
            return binarysearch(mid+1, j)
        return binarysearch(0, len(days))

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        if len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    '''
     [10,10,10,10,10,100], 
     m = 3, k = 2

    
    '''
    def checkBl(self,arr,day,m,k):
        
        cnt=0
        i=0
        start=0
        N=len(arr)
        while i<N:
            if arr[i]<=day:
                if start==k-1:
                    start=0
                    cnt+=1
                else:
                    start+=1
            else:
                start=0
            
            if cnt==m:
                return True
            
            i+=1
            
        return False
        
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m==0:
            return 0
        
        if m*k>len(bloomDay):
            return -1
        

        '''
        max_bd=float('-inf')
        min_bd=float('inf')
        
        for i in bloomDay:
            max_bd=max(max_bd,i)
            min_bd=min(min_bd,i)
         
        l=min_bd
        r=max_bd
        '''
        r=max(bloomDay)
        l=min(bloomDay)
        while  l<r:
            mid=(l+r)//2
            if self.checkBl(bloomDay,mid,m,k):
                r=mid
            else:
                l=mid+1
            
        return l
             
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1
        
        def canMakeBouquets(cap):
            nBouquets = 0
            nFlowers = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] > cap:
                    nFlowers = 0
                    continue
                nFlowers += 1
                if nFlowers == k:
                    nBouquets += 1
                    nFlowers = 0
            return nBouquets >= m
        
        lo, hi = min(bloomDay), max(bloomDay)
        while lo < hi:
            med = lo + (hi-lo)//2
            if canMakeBouquets(med):
                hi = med
            else:
                lo = med + 1
        return hi

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low = min(bloomDay)
        high = max(bloomDay) + 1

        def feasible(val):
            flowers = [True if val >= d else False for d in bloomDay]
            count = 0
            total = m

            while flowers:
                if flowers.pop():
                    count += 1
                else:
                    count = 0

                if count >= k:
                    total -= 1
                    count -= k
                    if total ==-1:
                        break
            return total <= 0
            

        while low < high:
            mid = (low + high) // 2

            if feasible(mid):
                high = mid
            else:
                low = mid + 1
        
        if low == max(bloomDay) + 1:
            return -1
        else:
            return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            cnt, n = 0, 0
            for b in bloomDay:
                if b <= mid:
                    n += (cnt + 1) // k
                    if n == m:
                        break
                    cnt = (cnt + 1) % k
                else:
                    cnt = 0
            if n == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if len(A) < m * k: return -1
        
        def count(v):
            ret, ct = 0, 0
            for a in A:
                if a <= v:
                    ct += 1
                else: ct = 0
                if ct == k:
                    ret += 1
                    ct = 0
            return ret
        
        left, right = min(A), max(A)
        while left < right:
            mid = (left + right) // 2
            if count(mid) < m:
                left = mid + 1
            else:
                right = mid
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def feasible(limit):
            flower=bouquets=0
            for day in bloomDay:
                if day<=limit:
                    bouquets+=(flower+1)//k
                    flower=(flower+1)%k
                else:
                    flower=0
                    
            return bouquets>=m
        
        
        if len(bloomDay)<m*k:return -1
    
        left,right=1,max(bloomDay)
        
        while left<right:
            
            mid=(left+right)//2
            
            if feasible(mid):
                right=mid
            
            else:
                left=mid+1
                
        return left
    
        
                    
                    
                    
                    
                    
                    
                
                
    
        


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A):
            return -1
        
        def isit(d):
            b = m
            for i, j in itertools.groupby(A, key=lambda x: x<=d):
                l = sum(1 for _ in j)
                if i==True:
                    b -= l//k
            return b<=0

        l = 0
        r = max(A)+1
        while l < r:
            mid = (l+r)//2
            if isit(mid):
                r = mid
            else:
                l = mid + 1
        print((l, r))
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        n = len(bloomDay)
        if n < m * k:
            return -1
        
        def check(x):
            cnt = 0
            i = 0
            for day in bloomDay:
                if day <= x:
                    i += 1
                    if i == k:
                        cnt += 1
                        i = 0
                    if cnt == m:
                        return True
                else:
                    i = 0
            return False
        
        days = sorted(set(bloomDay))
        
        lo, hi = 0, len(days) - 1
        while lo < hi:
            mid = (lo + hi)//2
            if check(days[mid]):
                hi = mid
            else:
                lo = mid + 1
        return days[hi] if check(days[hi]) else -1
        
                    
            


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A):
            return -1
        
        def isit(d):
            b = m
            for i, j in itertools.groupby(A, key=lambda x: x<=d):
                l = sum(1 for _ in j)
                if i==True:
                    b -= l//k
            return b<=0

        l = 0
        r = max(A)+1
        while l < r:
            mid = (l+r)//2
            if isit(mid):
                r = mid
            else:
                l = mid + 1
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def bouquets_possible(day):
            print(day)
            bouquets_count = 0
            conse_day = 0
            for i, v in enumerate(bloomDay):
                if v <= day:
                    conse_day += 1
                    if conse_day == k:
                        bouquets_count += 1
                        conse_day = 0
                else:
                    conse_day = 0
            print(bouquets_count)
            return bouquets_count
        
        if len(bloomDay) < m * k:
            return -1
        
        left = min(bloomDay)
        right = max(bloomDay)
        
        while left < right:
            mid = left + ( right - left)//2
            if bouquets_possible(mid) < m:
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def possible(x):
            flo, bq = 0, 0
            for bloom in bloomDay:
                if bloom > x:
                    flo = 0
                else:
                    flo += 1
                    if flo >= k:
                        flo = 0
                        bq += 1
            return bq >= m
        
        if m*k > len(bloomDay):
            return -1
        
        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left + right)//2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def possible(day):
            i=temp=b=0
            while i<len(bloomDay):
                if bloomDay[i]<=day:
                    temp+=1
                    if temp==k:
                        b+=1
                        temp=0
                        if b>=m:return True
                else:temp=0
                i+=1
            return False
        
        if len(bloomDay)<m*k:return -1
        
        left,right=min(bloomDay),max(bloomDay)
        while left<right:
            mid=left+(right-left)//2
            if possible(mid):
                right=mid
            else:
                left=mid+1
        return left

class Solution:
    def minDays(self, blooms: List[int], m: int, k: int) -> int:
        if m * k > len(blooms):
            return -1
        lo, hi = 0, max(blooms)

        def is_possible(today):
            streak = bouquets = 0

            for day in blooms:
                if day <= today:
                    streak += 1
                    if streak == k:
                        bouquets += 1
                        streak = 0
                else:
                    streak = 0

            return bouquets >= m

        while lo < hi:
            mid = (lo + hi) // 2
            if not is_possible(mid):
                lo = mid + 1
            else:
                hi = mid
        return lo

class Solution:
    '''
     [10,10,10,10,10,100], 
     m = 3, k = 2

    
    '''
    def checkBl(self,arr,day,m,k):
        
        cnt=0
        i=0
        start=0
        N=len(arr)
        while i<N:
            if arr[i]<=day:
                if start==k-1:
                    start=0
                    cnt+=1
                else:
                    start+=1
            else:
                start=0
            
            if cnt==m:
                return True
            
            i+=1
            
        return False
        
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m==0:
            return 0
        
        if m*k>len(bloomDay):
            return -1
        
        
        max_bd=float('-inf')
        min_bd=float('inf')
        
        for i in bloomDay:
            max_bd=max(max_bd,i)
            min_bd=min(min_bd,i)
            
        l=min_bd
        r=max_bd
        while  l<r:
            mid=(l+r)//2
            if self.checkBl(bloomDay,mid,m,k):
                r=mid
            else:
                l=mid+1
            
        return l
             
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        minDays = float('inf')
        maxDays = 0
        for bloomday in bloomDay:
            if (bloomday < minDays):
                minDays = bloomday
            if (bloomday > maxDays):
                maxDays = bloomday

        low = minDays
        high = maxDays
        mid = (low+high)//2

        while (low < high):
            if(self.validDays(mid, bloomDay, m, k)):
                high = mid
            else:
                low = mid+1
            mid = (low+high)//2

        if (self.validDays(low, bloomDay, m, k)):
            return low
        return -1

    def validDays(self, days, bloomDay, m, k):
        bouquets = 0
        idx = 0
        while(idx < len(bloomDay)):
            flowergroupcount = 0
            while (idx < len(bloomDay) and bloomDay[idx] <= days):
                flowergroupcount += 1
                idx += 1
            bouquets += flowergroupcount//k
            idx += 1
        if (bouquets >= m):
            return True
        return False

class Solution:
    def producedAfterqDays(self, garden, adj, q):
        wat = [i - q for i in garden]
        return sum([len(list(cgen)) // adj for c, cgen in itertools.groupby(wat, key=lambda w: w<=0) if c])
        
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # for i in range(100):
        #     if self.producedAfterqDays(bloomDay, k, i) >= m:
        #         return i
        # else:
        #     return -1
        l = 0
        r = max(bloomDay)
        ans = -1
        while l <= r:
            mid = (l + r)//2
            if self.producedAfterqDays(bloomDay, k, mid) >= m:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l = 1; r = int(1e9)
        def check(days, k):
            made = 0
            soFar = 0
            for i in range(len(bloomDay)):
                if(bloomDay[i] > days):
                    soFar = 0
                else:
                    soFar += 1
                if(soFar == k):
                    soFar = 0
                    made += 1
            return made
        while(l < r):
            mid = l+((r-l)>>1)
            if(check(mid, k) >= m):
                r = mid
            else:
                l = mid+1
        if(check(l, k) >= m):
            return l
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low,high = min(bloomDay),max(bloomDay)
        res = sys.maxsize
        while low <= high:
            med = (low+high)//2
            i = b = 0
            while i < len(bloomDay):
                f = 0
                while i < len(bloomDay) and bloomDay[i]<=med and f<k:
                    i, f = i+1, f+1
                if f==k:
                    b+=1
                    if b==m: break
                else: i+=1
            if b<m: low=med+1
            else:
                res=min(res,med) 
                high=med-1
        return res if res!=sys.maxsize else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = left + ((right - left) // 2)
            m1 = 0
            k1 = 0
            for f in range(len(bloomDay)):
                if bloomDay[f] <= mid:
                    if f == 0 or bloomDay[f - 1] <= mid:
                        k1 += 1
                    else:
                        k1 = 1
                    if k1 == k:
                        m1 += 1
                        k1 = 0
            if m1 >= m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, A, m, k):
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) / 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return int(left)

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def bouqets(d):
            res, c = 0, 0
            for n in bloomDay:
                c = 0 if n > d else c + 1
                if c == k:
                    res, c = res + 1, 0
            return res
            
        days = sorted(set(bloomDay))
        lo, hi = 0, len(days)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if bouqets(days[mid]) < m:
                lo = mid + 1
            else:
                hi = mid
        return days[hi] if days[hi] >= m else -1


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def count(d):
            total = 0
            curr = 0
            for i in range(len(bloomDay)):
                if bloomDay[i]>d:
                    curr = 0
                # else:
                #     curr += 1
                # if curr==k:
                #     total += 1
                else:
                    total += (curr + 1) // k
                    curr = (curr + 1) % k
            return total
        
        if m*k>len(bloomDay):
            return -1
        l = min(bloomDay)
        r = max(bloomDay)
        while l<r:
            d = l+(r-l)//2
            if count(d)>=m:
                r = d
            else:
                l = d+1
        return l

class Solution:
    def minDays(self, days: List[int], m: int, k: int) -> int:
        n = len(days)
        if m*k > n: return -1
        i, j = 1, max(days)
        while i < j:
            day = (i+j)/2
            bou = flow = 0
            for a in days:
                flow = 0 if a > day else flow+1
                if flow >= k:
                    flow = 0
                    bou += 1
                    if bou == m: break
            if bou == m:
                j = day
            else:
                i = day+1
            
        return int(i)



class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

        if len(bloomDay) < m*k:
            return -1


        def isPossible(l):
            i = 0
            temp = 0
            num_bouquets = 0
            while i < len(bloomDay):
                if bloomDay[i] > l:
                    temp = 0
                else:
                    temp += 1
                    if temp == k:
                        num_bouquets += 1
                        if num_bouquets == m:
                            return True
                        temp = 0

                i += 1

            return False


        low, high = min(bloomDay), max(bloomDay)
        while low < high:
            mid = low + (high-low)//2
            if isPossible(mid):
                high = mid
            else:
                low = mid+1
        return low



class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        A = bloomDay
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) / 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return int(left)

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left=min(bloomDay)
        right=max(bloomDay)
        def feasible(day):
            flower=0
            count=0
            for bloom in bloomDay:
                if bloom>day:
                    flower=0
                else:
                    count+=(flower+1)//k
                    flower=(flower+1)%k
                    
            return count>=m
                    
        if len(bloomDay)<m*k:
            return -1
        
        
            
        while left<right:
            mid=left+(right-left)//2
            if feasible(mid):
                right=mid
            else:
                left=mid+1
                
        return left


class Solution:
    def minDays(self, bloom: List[int], m: int, k: int) -> int:
        l, r = 1, max(bloom) + 1
        
        def do(t):
            j = 0
            ct = 0
            while j < len(bloom):
                i = j
                a = 0
                while i < len(bloom) and bloom[i] <= t:
                    a += 1
                    if a == k:
                        ct += 1
                        break
                    i += 1

                if ct == m:
                    return True
                
                j = i + 1
            return False
        
        while l < r:
            mid = (l + r) // 2
            
            if not do(mid):
                l = mid + 1
            else:
                r = mid
        
        return l if l <= max(bloom) else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay): return -1
        left=min(bloomDay)
        right=max(bloomDay)
        
        while left<right:
            mid=(left+right)//2
            print((left,right,mid,self.boquets(bloomDay,mid,k)))
            if self.boquets(bloomDay,mid,k)>=m:
                right=mid
            else:
                left=mid+1
    
        return left
    def boquets(self,bloom,day,k):
        res=0
        cur=0
        
        for d in bloom:
            if d<=day:
                cur+=1
            else:
                cur=0
            if cur==k:
                res+=1
                cur=0
        return res
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l = 1; r = max(bloomDay)
        def check(days, k):
            made = 0
            soFar = 0
            for i in range(len(bloomDay)):
                if(bloomDay[i] > days):
                    soFar = 0
                else:
                    soFar += 1
                if(soFar == k):
                    soFar = 0
                    made += 1
            return made
        while(l < r):
            mid = l+((r-l)>>1)
            if(check(mid, k) >= m):
                r = mid
            else:
                l = mid+1
        if(check(l, k) >= m):
            return l
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        bloomDayDict = defaultdict(list)
        
        for i, v in enumerate(bloomDay):
            bloomDayDict[v].append(i)
                    
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left if feasible(left) else -1

class Solution:
    
    
    
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m*k or k == 0: return -1
        if n == m*k: return max(bloomDay)
        
        def isGood(days):
            kk = 0
            mm = 0
            i = 0
            while i < len(bloomDay):
                if bloomDay[i] <= days:
                    while i < len(bloomDay) and bloomDay[i] <= days and kk < k:
                        i += 1        
                        kk += 1
                    if kk == k:
                        mm += 1
                        kk = 0
                else:
                    kk = 0
                    i += 1
                if mm == m:
                    return True
            return False
        
        low, high = 0, max(bloomDay)
        while low < high:
            mid = low + (high-low)//2
            if isGood(mid):
                high = mid
            else:
                low = mid+1
        return low
        
        
                        
            
                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def count(l,i):
            c,count=0,0
            for j in l:
                if(j<=i):
                    c+=1
                elif(j>i):
                    count+=c//k
                    c=0
            return count+c//k
        l=bloomDay[:]
        if((len(l)//k)<m):return -1
        l1=min(l)
        r=max(l)
        while(l1<r):
            mid=l1+(r-l1)//2
            if(count(l,mid)>=m):
                r=mid
            else:
                l1=mid+1
        return l1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low,high = 1,max(bloomDay)
        if m * k > len(bloomDay): return -1
        res = sys.maxsize
        while low <= high:
            med = (low+high)//2
            i = b = 0
            while i < len(bloomDay):
                f = 0
                while i < len(bloomDay) and bloomDay[i]<=med and f<k:
                    i, f = i+1, f+1
                if f==k: b+=1
                else: i+=1
            if b<m: low=med+1
            else:
                res=min(res,med) 
                high=med-1
        return res if res!=sys.maxsize else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canCreate(days):
            flowers = [1 if days >= bloom else 0 for bloom in bloomDay]
            bouquets = 0
            adj = 0
            for flower in flowers:
                if not flower:
                    adj = 0
                    continue
                adj += 1
                if adj == k:
                    adj = 0
                    bouquets += 1
                    if bouquets == m:
                        return True
            return False
        MAX = 10**9+1
        left, right = 1, MAX
        while left < right:
            mid = (left+right)//2
            if canCreate(mid):
                right = mid
            else:
                left = mid+1
        return left if left != MAX else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
    
        def check(flower,N,m,k):
            count=0
            for i in flower:
                if i==1:
                    count+=1
                    if count==k:
                        m-=1
                        count=0
                    if m==0:
                        return True
                else:
                    count=0
            return False
            
        
        N=len(bloomDay)
        if N<m*k:
            return -1
        left=0
        right=max(bloomDay)
        res=right
        while left<right:
            day=(left+right)//2
            flower=[0]*N
            for x in range(N):
                if bloomDay[x]<=day:
                    flower[x]=1  
  
            if check(flower,N,m,k):
                right=day
                res=min(res,day)
            else:
                left=day+1
            
        
        return res

                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        low=k
        high=min1=max(bloomDay)
        while low<=high:
            mid=(low+high)//2
            flag=sum1(mid,bloomDay,k)
            if flag>=m:
                high=mid-1
                min1=min(mid,min1)
            else:
                low=mid+1
                
        return min1
def sum1(given,bloom,k):
    res=0
    count=0
    i=0
    while i<len(bloom):
        if bloom[i]>given:
            i+=1
            count=0
            continue
        while i<len(bloom) and bloom[i]<=given:
            count+=1
            i+=1
            if count==k:
                res+=1
                count=0
    return res
                
                
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(x):
            currNumFlower, numBouquets = 0, 0
            for flower in bloomDay:
                currNumFlower+=1
                if flower > x:  currNumFlower=0
                else:
                    if currNumFlower == k:
                        currNumFlower, numBouquets = 0, numBouquets+1
            if numBouquets >= m:    return True
            return False
        
        left, right = 1, max(bloomDay)+1
        while left<right:
            mid = left + (right-left)//2
            if condition(mid):
                right = mid
            else:
                left = mid+1
        return left if left>0 and left<max(bloomDay)+1 else -1


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        start, end = 1, max(bloomDay)
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.helper(bloomDay, m, k, mid):
                end = mid
            else:
                start = mid
        
        if self.helper(bloomDay, m, k, start):
            return start
        elif self.helper(bloomDay, m, k, end):
            return end
        else:
            return -1
    
    def helper(self, bloomDay, m, k, day):
        consecutive = 0
        count = 0
        
        for bloomday in bloomDay:
            if bloomday > day:
                consecutive = 0
            else:
                consecutive += 1
                if consecutive == k:
                    count += 1
                    consecutive = 0
        
        return count >= m


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if len(bloomDay) < m*k:
            return -1
        
        def can_make(days):
            flowers = 0
            bouq = 0
            for i in bloomDay:
                if i > days:
                    flowers = 0
                else:
                    flowers += 1
                
                if flowers == k:
                    bouq += 1
                    flowers = 0
            
            return bouq >=m
                    
        
        left , right = 1 , max(bloomDay)
        while left < right:
            mid = left + (right- left) // 2
            
            if can_make(mid):
                right = mid
            
            else:
                left = mid + 1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low,high = min(bloomDay),max(bloomDay)
        if m * k > len(bloomDay): return -1
        res = sys.maxsize
        while low <= high:
            med = (low+high)//2
            i = b = 0
            while i < len(bloomDay):
                f = 0
                while i < len(bloomDay) and bloomDay[i]<=med and f<k:
                    i, f = i+1, f+1
                if f==k: b+=1
                else: i+=1
            if b<m: low=med+1
            else:
                res=min(res,med) 
                high=med-1
        return res if res!=sys.maxsize else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        
        def feasible(days) -> bool:
            
            bouquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m
    
        
        if len(bloomDay) < m * k:
            return -1
        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

'''
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        A = bloomDay
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left
'''
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m*k :return -1
        l, r = 1, max(bloomDay)
        while l < r:
            mid = l + (r - l) // 2
            temp = 0
            cnt = 0
            for n in bloomDay:
                temp = 0 if n > mid else temp + 1
                if temp >=k:
                    temp = 0
                    cnt+=1
                    if cnt==m:break
            if cnt == m : r= mid
            else: l = mid+1
        return l



class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        def get_num_boquets(wait_days):
            i = 0
            while i < n and bloomDay[i] > wait_days:
                i += 1
            # i: index of first available flower
            j = i
            count = 0
            while j < n:
                while j < n and bloomDay[j] <= wait_days:
                    j += 1
                j -= 1 # index of last available flower in the adjacent subarray
                count += (j-i+1) // k
                i = j + 1
                while i < n and bloomDay[i] > wait_days:
                    i += 1
                # i: index of first available flower
                j = i
            return count
        start = 1
        end = max(bloomDay)
        while start < end:
            mid = start + (end-start) // 2
            #print(mid, get_num_boquets(mid))
            if get_num_boquets(mid) >= m:
                # wait is too long, or just right
                end = mid
            else:
                # wait is too short
                start = mid + 1
        if start >= 1 and start <= max(bloomDay) and get_num_boquets(start) >= m:
            return start
        else:
            return -1


from array import array

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        if k == 0:
            return 0
        
        min_d, max_d = bloomDay[0], bloomDay[0]
        
        for d in bloomDay:
            if d > max_d:
                max_d = d
            if d < min_d:
                min_d = d
        
        def possible_bouquets(day):
            bouquets = 0
            flower_count = 0
            i = 0
            while i < len(bloomDay):
                if bloomDay[i] <= day:
                    flower_count += 1
                    
                    if flower_count == k:
                        bouquets+=1
                        flower_count = 0
                else:
                    flower_count = 0
                i+=1
            return bouquets
            
        possible_days = -1
        day_guess = (min_d + max_d) // 2
        
        while min_d <= max_d:
            bouquets = possible_bouquets(day_guess)
            #print(f\"{day_guess}:{bouquets}\")
            if bouquets >= m:
                max_d = day_guess - 1
                possible_days = day_guess
            else:
                min_d = day_guess + 1
            
            day_guess = (min_d + max_d) // 2
            
        return possible_days


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low,high = min(bloomDay),max(bloomDay)
        res = sys.maxsize
        while low <= high:
            med = (low+high)//2
            i = b = 0
            while i < len(bloomDay):
                f = 0
                while i < len(bloomDay) and bloomDay[i]<=med and f<k:
                    i, f = i+1, f+1
                if f==k: b+=1
                else: i+=1
            if b<m: low=med+1
            else:
                res=min(res,med) 
                high=med-1
        return res if res!=sys.maxsize else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def checkFlowers(mid,m,k):
            bq = 0
            i = 0
            while i <len(bloomDay):
                if bloomDay[i] <= mid:
                    count = 1
                    i+=1
                    while i <len(bloomDay) and count < k and bloomDay[i] <= mid:
                        count+=1
                        i+=1
                    if count == k:
                        bq+=1
                else:
                    i+=1
            return bq
        
        
        if len(bloomDay) < k*m :
            return -1
        
        low = 1
        high = max(bloomDay)
        while low < high:
            mid = (low + high)//2
            x = checkFlowers(mid,m,k) 
            if x >= m:
                high = mid
            else:
                low = mid + 1
        return high

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        low = min(bloomDay)
        high = max(bloomDay) + 1

        def feasible(val):
            flowers = list(map(lambda f: val >= f, bloomDay))
            count = 0
            total = m

            while flowers:
                if flowers.pop():
                    count += 1
                else:
                    count = 0

                if count >= k:
                    total -= 1
                    count -= k
                    if total ==-1:
                        break
            return total <= 0
            

        while low < high:
            mid = (low + high) // 2

            if feasible(mid):
                high = mid
            else:
                low = mid + 1
        
        if low == max(bloomDay) + 1:
            return -1
        else:
            return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1

        bloomDay_sort = sorted(bloomDay)
        bloomDay_dict = {}
        num = 0
        prev = -1
        for item in bloomDay_sort:      # 离散
            if item != prev:
                bloomDay_dict[num] = item
                num += 1
                prev = item

        # 二分day
        bloomDay_tmp = [0 for ii in range(len(bloomDay))]
        l, r = 0, num
        while l < r:
            mid = (l+r)//2
            for i in range(len(bloomDay)):
                if bloomDay[i] <= bloomDay_dict[mid]:
                    bloomDay_tmp[i] = 1
                else:
                    bloomDay_tmp[i] = 0

            count_nonlocal = 0
            count = 0
            for i in range(len(bloomDay_tmp)):
                if bloomDay_tmp[i] == 1:
                    count += 1
                else:
                    count_nonlocal += count // k
                    count = 0

            if count != 0:          ##
                count_nonlocal += count // k
                count = 0

            if count_nonlocal >= m:
                r = mid
            else:
                l = mid+1

        return bloomDay_dict[l]      # 

class Solution:
    def minDays(self, bd: List[int], no_of_bouqs: int, flowers_in_a_bouq: int) -> int:
        if len(bd)<no_of_bouqs*flowers_in_a_bouq:
            return -1
        def condition(minDays):
            #print(minDays,end=' ')
            bouq=0; bouq_flowers=0
            for i in bd:
                if i<=minDays:  # The flower can be used
                    bouq_flowers+=1
                    if bouq_flowers==flowers_in_a_bouq:
                        bouq+=1
                        bouq_flowers=0
                        if bouq==no_of_bouqs:
                            return True
                if i>minDays:
                    bouq_flowers=0
                #print(i,minDays,bouq_flowers,bouq)
            return False
        
        l=min(bd)
        r=max(bd)
        while l<r:
            mid=(l+r)//2
            if condition(mid):
                r=mid
            else:
                l=mid+1
        return l

class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        
        def valid(mid):
            cur = 0
            accu = 0
            for n in A:
                if n <= mid:
                    cur += 1
                    if cur == k:
                        accu += 1
                        cur = 0
                else:
                    cur = 0
            return accu >= m
        
        n = len(A)
        if m * k > n: return -1
        
        l, r = min(A), max(A)
        while l < r:
            mid = (l+r)//2
            if valid(mid): r = mid
            else: l = mid + 1
        return l
        
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        lo, hi = float('inf'), -float('inf')
        for day in bloomDay:
            lo = min(lo, day)
            hi = max(hi, day)
        
        def check(d): # check if D days is good enough for m bouquets of k flowers
            cnt, start = 0, -1
            for i, val in enumerate(bloomDay):
                if val <= d and i - start >= k:
                    cnt += 1
                    start = i
                elif val > d:
                    start = i
            return cnt >= m
        
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def make_boquets(mid):
            flowers,bouquets = 0,0
            for flower in bloomDay:
                if flower > mid:
                    flowers = 0
                else:
                    flowers += 1
                    if flowers == k:
                        flowers = 0
                        bouquets += 1
            return bouquets >= m
        left,right = min(bloomDay), max(bloomDay) + 1
        while left < right:
            mid = left + (right-left)//2
            if make_boquets(mid):
                right = mid
            else:
                left = mid + 1
        if left > max(bloomDay):
            return -1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def bouqets(d):
            res, c = 0, 0
            for n in bloomDay:
                c = 0 if n > d else c + 1
                if c == k:
                    res, c = res + 1, 0
            return res
            
        days = sorted(set(bloomDay))
        lo, hi = 0, len(days)-1
        while lo < hi:
            mid = (lo + hi) // 2
            bouq, c = 0, 0
            for n in bloomDay:
                c = 0 if n > days[mid] else c + 1
                if c == k:
                    bouq, c = bouq + 1, 0
            if bouq < m:
                lo = mid + 1
            else:
                hi = mid
        return days[hi] if bouqets(days[hi]) >= m else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def condition(x):
            bloom = [0]*len(bloomDay)
            for i, day in enumerate(bloomDay):
                if day <= x:
                    bloom[i] = 1
            count = 0
            M = 0
            for flower in bloom:
                if flower:
                    count += 1
                else:
                    count = 0
                if count >= k:
                    count = 0
                    M += 1
                if M >= m:
                    return True
            return False

        if len(bloomDay) < m*k: return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def make_boquets(mid):
            i,boquets = 0,0
            while i < len(bloomDay):
                j = i
                while j < len(bloomDay) and j - i < k:
                    if bloomDay[j] > mid:
                        break
                    j += 1
                if j-i == k:
                    boquets += 1
                    j -= 1
                i = j + 1
            return boquets >= m
        left,right = min(bloomDay), max(bloomDay) + 1
        while left < right:
            mid = left + (right-left)//2
            if make_boquets(mid):
                right = mid
            else:
                left = mid + 1
        if left > max(bloomDay):
            return -1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        '''
        # Notes:
            k adjacent flowers
        
        '''
        # edge case
        n = len(bloomDay)
        if n // k < m:
            return -1
        if k * m == n:
            return max(bloomDay)
        
        def feasible(days) -> bool:
            bonquets, flowers = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bonquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bonquets >= m

        if len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)<m*k:
            return -1
        
        def canMake(days, bloomDay, k):
            flowers, n = 0, 0
            for bloom in bloomDay:
                if bloom>days:
                    flowers = 0
                else:
                    n = n + (flowers+1)//k
                    flowers = (flowers+1)%k
            return n
                    
        # use binary search. search values are
        # within min(bloomDay) and max(bloomDay)
        l, r = min(bloomDay), max(bloomDay)
        while l<=r:
            mid = l+(r-l)//2
            count = canMake(mid, bloomDay, k)
            if count==m:
                r = mid-1
            elif count<m:
                l = mid+1
            elif count>m:
                r = mid-1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(day):
            bouquets = 0
            adjacent = 0
            for bloom in bloomDay:
                if bloom > day:
                    adjacent = 0
                else:
                    adjacent += 1
                
                if adjacent == k:
                    bouquets += 1
                    adjacent = 0
            
            return bouquets >= m
            
        
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left if feasible(left) else -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days: int):
            flowers, bouquets = 0, 0
            for bloom in bloomDay:
                if bloom > days:
                    flowers = 0
                else:
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
            return bouquets >= m

        if len(bloomDay) < m * k: return -1
        low, high = 1, max(bloomDay)
        while low < high:
            mid = low + (high - low) // 2
            if feasible(mid):
                high = mid
            else:
                low = mid + 1
        return low




class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay): return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in bloomDay:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if self.validBouquets(bloomDay, mid, m, k):
                right = mid
            else:
                left = mid + 1
        return left
    
    def validBouquets(self, bloomDay, days, m, k):
        # Count how many bouquets we can collect
        count_bouquets = 0
        temp_flowers = 0
        for bloom in bloomDay:
            if bloom <= days:
                temp_flowers += 1
            else:
                temp_flowers = 0
            # Determine whether flowers in hand can form a bouquet
            if temp_flowers >= k:
                count_bouquets += 1
                temp_flowers = 0
        return count_bouquets >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def make_boquets(mid):
            i,boquets = 0,0
            while i < len(bloomDay):
                j = i
                while j < len(bloomDay) and j - i < k:
                    if bloomDay[j] > mid:
                        break
                    j += 1
                if j-i == k:
                    boquets += 1
                    j -= 1
                i = j + 1
            return boquets >= m
        if len(bloomDay) < m * k:
            return -1
        left,right = min(bloomDay), max(bloomDay) + 1
        while left < right:
            mid = left + (right-left)//2
            if make_boquets(mid):
                right = mid
            else:
                left = mid + 1
        if left > max(bloomDay):
            return -1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
#         binary search
        def validable(days):
#             how many booms in days, and how many bouquet can make
            bloom = 0
            bouquet = 0
            for b in bloomDay:
                if b <= days:
                    bloom += 1
                    bouquet += bloom // k
                    bloom = bloom % k
                else:
                    bloom = 0
            return bouquet >= m
                    
        if len(bloomDay) < m * k:
            return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if validable(mid):
                right = mid
            else:
                left = mid + 1
        return left
    
    
    
#     def minDays(bloomDay: List[int], m: int, k: int) -> int:
#     def feasible(days) -> bool:
#         bonquets, flowers = 0, 0
#         for bloom in bloomDay:
#             if bloom > days:
#                 flowers = 0
#             else:
#                 bonquets += (flowers + 1) // k
#                 flowers = (flowers + 1) % k
#         return bonquets >= m

#     if len(bloomDay) < m * k:
#         return -1
#     left, right = 1, max(bloomDay)
#     while left < right:
#         mid = left + (right - left) // 2
#         if feasible(mid):
#             right = mid
#         else:
#             left = mid + 1
#     return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if len(bloomDay)<m*k:
            return -1
        l,r=1,max(bloomDay)
        
        def feasible(days):
            flowers,bouquets=0,0
            for bloom in bloomDay:
                if bloom>days:
                    flowers=0
                else:
                    bouquets+=(flowers+1)//k
                    flowers=(flowers+1)%k
            return bouquets>=m
        
        while l<r:
            mid=(l+r)//2
            if feasible(mid):
                r=mid
            else:
                l=mid+1
        return l


class Solution:
    def bloom(self,arr,k,d,m):
        cnt,bk=0,0
        for i in arr:
            if i<=d:
                cnt+=1
                if cnt==k:
                    bk+=1
                    cnt=0
            else:
                cnt=0
        if bk>=m:
            return 1
        else:
            return 0
            
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l=1
        r=max(bloomDay)+1
        while l<r:
            mid=(l+r)//2
            if self.bloom(bloomDay,k,mid,m):
                r=mid
            else:
                l=mid+1
        return -1 if l>max(bloomDay) else l       

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
    
        def can_make(days):
            num_boqs = 0
            num_flows = 0
            
            start = 0
            
            for bloom in bloomDay:
                if bloom > days:
                    num_flows = 0
                else:
                    num_boqs += (num_flows + 1) // k
                    num_flows = (num_flows + 1) % k
                    
            return num_boqs >= m
            
        if len(bloomDay) < m * k:
            return -1
        
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if can_make(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def feasible(days) -> bool:
            flowers = 0
            bouquets = 0
            
            #loop through the array to check the days to bloom
            for bloom in bloomDay:
                if bloom > days: #we cannot gather any flowers to make the bouquets because the flower are not yet bloomed 
                    flowers = 0
                    
                else: 
                    bouquets += (flowers + 1) // k
                    flowers = (flowers + 1) % k
                    
            return bouquets >= m
        
            
        
        
        #base case: 
        if len(bloomDay) < m * k:
            return -1
        left = 1
        right = max(bloomDay)
        while left < right: 
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
                
            else: 
                left = mid + 1
                
        return left
    


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        left = 1
        right = max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flow = 0
            bouq = 0
            for n in bloomDay:
                if n > mid:
                    flow = 0
                else:
                    flow += 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m:
                        break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        s = 0
        e = max(bloomDay)
        ans = -1
        
        while s <= e:
            mid = int(s + (e-s)/2)
            if self.checkDay(bloomDay, m, k, mid):
                ans = mid
                e = mid - 1
            else:
                s = mid + 1
        
        return ans
    
    def checkDay(self, a, m, k, d):
        tot = 0
        count = 0
        for i in range(len(a)):
            if a[i] <= d:
                count+=1
                if count == k:
                    tot += 1
                    count = 0
            else:
                count = 0
        
        return tot >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        lo, hi = min(bloomDay), max(bloomDay)
        def validDay(bloom, day):
            cnt, adj = 0, 0
            for b in bloom:
                if b <= day:
                    adj += 1
                if adj >= k:
                    adj = 0
                    cnt += 1
                if b > day:
                    adj = 0
            print((cnt, k))
            return cnt >= m
        while lo < hi:
            mid = (lo + hi) // 2
            if validDay(bloomDay, mid):
                hi = mid
            else:
                lo = mid + 1
        return lo


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        min_day = bloomDay[0]
        max_day = bloomDay[0]
        for day in bloomDay:
            if min_day > day:
                min_day = day
            if max_day < day:
                max_day = day

        def isValidDay(day_try: int) -> bool:
            count = 0
            current = 0
            for local_day in bloomDay:
                if day_try >= local_day:
                    current += 1
                    if current >= k:
                        count += 1
                        current = 0
                else:
                    current = 0
            return count >= m

        left = min_day
        right = max_day
        result = 0
        while left <= right:
            mid = (left + right) // 2
            if isValidDay(mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        return result

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l = 1
        r = 1000000000
        if m * k > len(bloomDay):
            return -1
        
        while l < r:
            
            mid = l + (r - l)//2
            if self.validflower(mid, bloomDay, k, m) == True:
                r = mid
            else:
                l = mid + 1
        return l         
            
 
            
    def validflower(self, mid, bloomDay, k, m):
        count = 0
        f = 0
        for j in bloomDay:
            if j <= mid:
                f += 1
            else:
                f = 0
                
            if f == k:
                count += 1
                f = 0
            
        if count >= m:
            return True
        
        return False
                


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        len_bloom = len(bloomDay)
        lis = [[bloomDay[i], i] for i in range(len_bloom)]
        lis.sort()
        lis2 = [[] for x in range(len_bloom)]
        tot = 0
        for i in lis:
            val, index = i
            if(index > 0 and lis2[index-1] and index < len_bloom-1 and lis2[index+1]):
                start = lis2[index-1][0]
                end = lis2[index+1][1]
                tot -= (lis2[index-1][3] + lis2[index+1][3])
                tot_len = lis2[index-1][2] + 1 + lis2[index+1][2]
                tot += tot_len//k
                to_be_inserted = [start, end, tot_len, tot_len//k]
                lis2[start] = to_be_inserted
                lis2[end] = to_be_inserted
            elif(index > 0 and lis2[index-1]):
                start = lis2[index-1][0]
                end = index
                tot -= lis2[index-1][3]
                tot_len = lis2[index-1][2] + 1
                tot += tot_len//k
                lis2[start] = [start, end, tot_len, tot_len//k]
                lis2[end] = lis2[start]
            elif(index < len_bloom - 1 and lis2[index+1]):
                start = index
                end = lis2[index+1][1]
                tot -= lis2[index+1][3]
                tot_len = lis2[index+1][2] + 1
                tot += tot_len//k
                lis2[end] = [start, end, tot_len, tot_len//k]
                lis2[start] = lis2[end]
            else:
                tot += 1//k
                lis2[index] = [index, index, 1, 1//k]
            if(tot >= m):
                return val
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1
        lo , hi = min(bloomDay), max(bloomDay)
        while lo<hi:
            mid=(lo+hi)//2
            i, cap, bqts = 0, 0, 0
            while i<len(bloomDay):
                if bloomDay[i]<=mid: 
                    cap+=1
                else:
                    cap=0
                if cap==k:
                    bqts+=1
                    cap=0
                i+=1  
            if bqts<m:
                lo=mid+1
            else:
                hi=mid
        return lo
                    
                    


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n=len(bloomDay)
        events=sorted(bloomDay)
        
        def possible(time):
            flower = [j for j, i in enumerate(bloomDay) if i<=time]
            left=0
            bouquets=0
            for i, c in enumerate(flower):
                if i==len(flower)-1 or flower[i+1]!=c+1:
                    bouquets+=(i-left+1)//k
                    left=i+1
            return bouquets>=m
        
        lo, hi = 0, n
        while lo<hi:
            mid = lo+(hi-lo)//2 #prevent overflow
            if not possible(events[mid]):
                lo=mid+1
            else:
                hi=mid
        return events[lo] if lo<n else -1
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n=len(bloomDay)
        events=sorted(list(set(bloomDay)))
        
        def possible(time):
            flower = [j for j, i in enumerate(bloomDay) if i<=time]
            left=0
            bouquets=0
            for i, c in enumerate(flower):
                if i==len(flower)-1 or flower[i+1]!=c+1:
                    bouquets+=(i-left+1)//k
                    left=i+1
            return bouquets>=m
        
        lo, hi = 0, len(events)
        while lo<hi:
            mid = lo+(hi-lo)//2 #prevent overflow
            if not possible(events[mid]):
                lo=mid+1
            else:
                hi=mid
        return events[lo] if lo<len(events) else -1
            


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A): 
            return -1
        left, right = 1, max(A)
        while left <= right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid - 1
            else:
                left = mid + 1
        return left
            
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def feasible_bloom_day(value):
            total_bouquet = 0
            num_flowers = 0
            
            for bloom in bloomDay:
                # Flower bloomed
                if bloom > value:
                    num_flowers = 0
                else:
                    total_bouquet += (num_flowers+1) // k
                    num_flowers = (num_flowers+1) % k
            
            return total_bouquet >= m
        
        left, right = 1, max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if feasible_bloom_day(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # day d how many bouquets we could make
        if m*k > len(bloomDay):
            return -1
        
        
        def count(d):
            ans = 0
            curr = 0
            
            for i in range(len(bloomDay)):
                if bloomDay[i] <= d:
                    curr += 1
                    if curr == k:
                        ans += 1
                        curr = 0
                else:
                    curr = 0
            return ans
        
        l, r = 1, max(bloomDay)
        
        while l < r:
            mid = (l + r) //2
            print((l, r, mid, count(mid)))
            if count(mid) >= m:
                r = mid
            else:
                l = mid + 1
        
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        vals = list(set(bloomDay))
        vals.sort()
        
        def invalid(threshold):
            cur = 0
            bouquets = 0
            for x in bloomDay:
                if x <= threshold:
                    cur += 1
                    if cur == k:
                        cur = 0
                        bouquets += 1
                else:
                    cur = 0
            return bouquets < m
        
        left, right = 0, len(vals) - 1
        while left <= right:
            mid = (left + right) // 2
            # print(left, right, mid)
            if invalid(vals[mid]):
                left = mid + 1
            else:
                right = mid - 1
        return vals[left]

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def isOK(day, m):
            cur = 0
            for ptr in range(len(bloomDay)):
                if bloomDay[ptr] > day:
                    cur = 0
                else:
                    cur += 1
                    if cur == k:
                        m -= 1
                        cur = 0
                        if m == 0:
                            return True
            return False
            
        if m * k > len(bloomDay):
            return -1
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if isOK(mid, m):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(days):
            ans = 0
            temp = k
            func = lambda x : 1 if x <= days else 0
            nums = [func(i) for i in bloomDay]
            
            for i in nums:
                if i == 0:
                    temp = k
                else:
                    if temp == 1:
                        temp = k
                        ans += 1
                    else:
                        temp -= 1
            return ans >= m
               
        n = len(bloomDay)
        if n < m * k:
            return -1
        
        l,r = 0,max(bloomDay)
        while l <= r:
            mid = (l+r) // 2
            if check(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
    
        if m*k>len(bloomDay):
            return -1
        l=1
        r=max(bloomDay)
        while l<=r:
            mid=(l+r)//2
            count=0
            b=0
            for i in range(len(bloomDay)):
                if bloomDay[i]<=mid:
                    count+=1
                if count%k==0 and count!=0:
                    b+=1
                    count=0
                if bloomDay[i]>mid:
                    count=0
            if b>=m:
                
                r=mid-1
            else:
                l=mid+1
        return l
                
                
                
                
            
        
        
        
                        
            
                
            
        
        
        
        
        
        
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if not bloomDay or m*k > len(bloomDay):
            return -1
        mx = max(bloomDay)
        mn = min(bloomDay)
        l = mn
        r = mx
        not_possible = False
        while l < r:
            day = (l+r) // 2
            p = self.works(day, bloomDay, m, k)
            if p:
                r = day
            else:
                l = day+1
            #if l >= r and not p:
            #    not_possible = True
        
        return l if not not_possible else -1
    
    def works(self, day, arr, m, k):
        ktmp = k
        for i in range(len(arr)):
            n = arr[i]
            if n <= day:
                ktmp -= 1
                if ktmp == 0:
                    ktmp = k
                    m -= 1
                if m == 0:
                    return True
            else:
                ktmp = k
        return False
                    
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left = min(bloomDay)
        right = max(bloomDay)
        max_day = right
        
        
        def check(days):
            num = 0
            count = 0
            for i in bloomDay:
                if i <= days:
                    count+=1
                    if count == k:
                        num += 1
                        count = 0
                else:
                    count = 0
            return num >= m
        
        while left < right:
            mid = (left+right)>>1
            if check(mid) == True:
                right = mid
            else:
                left = mid+1
        
        if left == max_day and check(left) != True:
            return -1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def count(d):
            total = 0
            curr = 0
            for i in range(len(bloomDay)):
                if bloomDay[i]>d:
                    curr = 0
                else:
                    curr += 1
                if curr==k:
                    total += 1
                    curr = 0
                # else:
                #     total += (curr + 1) // k
                #     curr = (curr + 1) % k
            return total
        
        if m*k>len(bloomDay):
            return -1
        l = min(bloomDay)
        r = max(bloomDay)
        while l<r:
            d = l+(r-l)//2
            print(l, r, d, count(d))
            if count(d)>=m:
                r = d
            else:
                l = d+1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def binarySearch(bloomDay, m, k, smallest, longest):
            waitDay = (smallest + longest) // 2
            totalCount = 0
            currentCount = 0
            # print(\"-=-=-=-=-=-=-=-=-=-=-=-=-=\")
            # print(smallest)
            # print(longest)
            for i in range(len(bloomDay)):
                if bloomDay[i] <= waitDay:
                    currentCount += 1
                else:
                    currentCount = 0
                
                if currentCount == k:
                    totalCount += 1
                    currentCount = 0
            if totalCount >= m:
                if smallest == waitDay:
                    return waitDay
                else:
                    checkSmaller = binarySearch(bloomDay, m, k, smallest, waitDay - 1)
                    if checkSmaller != -1:
                        return checkSmaller
                    else:
                        return waitDay
            else:
                if waitDay == longest:
                    return -1
                else:
                    return binarySearch(bloomDay, m, k, waitDay + 1, longest)
        
        if m * k > len(bloomDay):
            return -1
        else:
            return binarySearch(bloomDay, m, k, 0, max(bloomDay))

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # arr[i] = time after which we can use index i, k = no. of adjacent flowers , m = no. of boquet
        # ans = min. no of days to make m boquet else -1
        
        # arr = [1,10,3,4,10,2] m = 3 k = 2
        # ans = 10
        
        # after d will there be m subarrays with k elements each?
        
        def feasible(d) -> bool:
            # m separate subbarr of size k where max val in each subarr <= d
            count = 0
            prevBadIndex = -1
            for i in range(len(bloomDay)):
                if bloomDay[i] > d:
                    count += (i - prevBadIndex - 1) // k
                    prevBadIndex = i
            
            if prevBadIndex != len(bloomDay) - 1:
                count += (len(bloomDay) - prevBadIndex - 1) // k
            
            return count >= m
        
        if len(bloomDay) < (m * k):
            return -1
        
        
        left,right = min(bloomDay), max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        min_day = min(bloomDay)
        max_day = max(bloomDay)
        lbd = len(bloomDay)
        
        if lbd < m*k:
            return -1
        
        while min_day < max_day:
            mid = (min_day + max_day - 1)//2
            
            nk, nm = 0, 0
            for i in range(lbd):
                
                if bloomDay[i] <= mid:
                    nk += 1
                else:
                    nk = 0
                if nk >= k:
                    nm += 1
                    nk = 0
            if nm < m:
                min_day = mid + 1
            else:
                max_day = mid
            
        return min_day
                    
            
            
            
        
        
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        low = 0
        high = max(bloomDay)
        
        if m*k > len(bloomDay):
            return -1
        
        def can_make_bouquets(mid):
            days = 0
            curr = [0]*len(bloomDay)
            for i in range(len(bloomDay)):
                if bloomDay[i] <= mid:
                    if i == 0:
                        curr[i] = 1
                    elif curr[i-1] == k:
                        curr[i] = 1
                    else:
                        curr[i] = curr[i - 1] + 1
            
            if curr.count(k) >= m:
                return True
            
            return False
            
        while low < high:
            mid = math.floor((low+high)/2)
            if can_make_bouquets(mid):
                high = mid
            else:
                low = mid +1
        
        return low 


from typing import List

def binarysearch(start, end, condition):
    l, r = start, end
    while l < r:
        mid = l + (r - l) // 2
        if condition(mid):
            r = mid
        else:
            l = mid + 1
    return l


class Solution:
    def minDays(self, bloomDay, m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1

        def canMakeBouquet():
            def condition(day):
                count = 0
                curr = 0
                for b_day in bloomDay:
                    has_bloomed = day >= b_day
                    if has_bloomed:
                        curr += 1
                        if curr == k:
                            curr = 0
                            count += 1
                    else:
                        curr = 0

                    if count >= m:
                        return True

                return False

            return condition

        return binarysearch(0, max(bloomDay), canMakeBouquet())




class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        def fesible(mid):
            c,n,l = 0,0,[]
            b=[(i-mid) for i in bloomDay] 
            # print(b)
            for i in range(len(b)):
                # print(l)
                if b[i]<=0 and i!=(len(b)-1):
                    c+=1
                elif b[i]<=0 and i==(len(b)-1):
                    ##
                    c+=1
                    l.append(c)
                elif b[i]>0:
                    l.append(c)
                    c=0
            
            # print(l)
            l2=[j for j in l if j>=k]
            ss=0
            for i in l2:
                ss+=i//k
            if ss>=m or m*k<=max(l):
                return True
            return False
        
        v=0
        left, right = min(bloomDay), max(bloomDay)+1
        while left<right:
            mid = left + (right-left)//2
            # print(mid)
            if fesible(mid):
                right=mid
                v=1
            else:
                left = mid +1
        if v==0:
            return -1
        return left
    
    
    
        



from typing import List

def binarysearch(start, end, condition, postprocessing):
    l, r = start, end
    while l < r:
        mid = l + (r - l) // 2
        if condition(mid):
            r = mid
        else:
            l = mid + 1
    return postprocessing(l)


class Solution:
    def minDays(self, bloomDay, m: int, k: int) -> int:
        def canMakeBouquet():
            def condition(day):
                count = 0
                curr = 0
                for b_day in bloomDay:
                    has_bloomed = day >= b_day
                    if has_bloomed:
                        curr += 1
                        if curr == k:
                            curr = 0
                            count += 1
                    else:
                        curr = 0

                    if count >= m:
                        return True

                return False

            return condition

        def maybeCantMake(final_day):
            return -1 if not canMakeBouquet()(final_day) else final_day

        return binarysearch(0, max(bloomDay), canMakeBouquet(), maybeCantMake)




class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        def fesible(mid):
            c,l = 0,[]
            b=[(i-mid) for i in bloomDay] 
            # print(b)
            for i in range(len(b)):
                # print(l)
                if b[i]<=0 and i!=(len(b)-1):
                    c+=1
                elif b[i]<=0 and i==(len(b)-1):
                    ##
                    c+=1
                    l.append(c)
                elif b[i]>0:
                    l.append(c)
                    c=0
        
            ss=0
            for i in l:
                ss+=i//k
            if ss>=m:
                return True
            return False
        
        v=0
        left, right = min(bloomDay), max(bloomDay)+1
        while left<right:
            mid = left + (right-left)//2
            if fesible(mid):
                right=mid
                v=1
            else:
                left = mid +1
        if v==0:
            return -1
        return left
    
    
    
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMake(bloomDay, m, k, day):
            bloom = []
            for bday in bloomDay:
                if bday <= day:
                    bloom.append(1)
                else:
                    bloom.append(-1)
            r, cur, cnt = 0, 0, 0
            while r < len(bloomDay):
                if bloom[r] == 1:
                    cur += 1
                    if cur == k:
                        cnt += 1
                        cur = 0
                        if cnt == m:
                            return True
                else:
                    cur = 0
                r += 1
            return False
        if m*k > len(bloomDay):
            return -1
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if not canMake(bloomDay, m, k, mid):
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        def fesible(mid):
            c,n,l = 0,0,[]
            b=[(i-mid) for i in bloomDay] 
            # print(b)
            for i in range(len(b)):
                # print(l)
                if b[i]<=0 and i!=(len(b)-1):
                    c+=1
                elif b[i]<=0 and i==(len(b)-1):
                    ##
                    c+=1
                    l.append(c)
                elif b[i]>0:
                    l.append(c)
                    c=0
        
            ss=0
            for i in l:
                ss+=i//k
            if ss>=m:
                return True
            return False
        
        v=0
        left, right = min(bloomDay), max(bloomDay)+1
        while left<right:
            mid = left + (right-left)//2
            # print(mid)
            if fesible(mid):
                right=mid
                v=1
            else:
                left = mid +1
        if v==0:
            return -1
        return left
    
    
    
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def bouqets(d):
            res = 0
            c = 0
            for n in bloomDay:
                if n <= d:
                    c += 1
                else:
                    c = 0
                
                if c == k:
                    res += 1
                    c = 0
            return res
            
        days = sorted(set(bloomDay))
        lo, hi = 0, len(days)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if bouqets(days[mid]) < m:
                lo = mid + 1
            else:
                hi = mid
        return days[hi] if days[hi] >= m else -1
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l, r = 1, max(bloomDay)
        while l + 1 < r:
            mid = (l + r) // 2
            if self.is_ok(bloomDay, mid, m, k):
                r = mid
            else:
                l = mid
        if self.is_ok(bloomDay, l, m, k):
            return l
        if self.is_ok(bloomDay, r, m, k):
            return r
        return -1
    
    def is_ok(self, bloomDay, target, m, k):
        flowers = 0
        for remain in bloomDay:
            if remain <= target:
                flowers += 1
                if flowers == k:
                    m -= 1
                    flowers = 0
            else:
                flowers = 0
        
        return m <= 0


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        
        #divide array into m parts or more, each part has at least k elements, minimize the maximum values of parts
        if len(A) < m*k:
            return -1
        
        def canSplit(T):
            count = 0
            cur = 0
            i = 0
            for x in A:
                cur = max(cur, x)
                i += 1
                if cur > T:
                    cur = 0
                    i = 0
                elif i==k:
                    cur = 0
                    i = 0
                    count += 1
            return count >= m
        
        l = min(A)
        r = max(A)
        
        while l < r:
            mid = l + (r-l)//2
            if canSplit(mid):
                r = mid
            else:
                l = mid + 1
        return l
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def is_possible(days) -> bool:
            bouquets = 0
            flowers = 0
            for bloom in bloomDay:
                if bloom <= days:
                    flowers += 1
                    if flowers >= k:
                        bouquets += 1
                        flowers = 0
                        if bouquets >= m:
                            return True
                else:
                    flowers = 0
            return False

        if len(bloomDay) < m * k:
            return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            days = left + (right - left) // 2
            if is_possible( days ):
                right = days
            else:
                left = days + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        def canmake(days):
            b = 0
            f = 0
            
            for d in bloomDay:
                if d <= days:
                    b += (f + 1) // k
                    f = (f + 1) % k
                else:
                    f = 0
            
            return b >= m

        left = min(bloomDay)
        right = max(bloomDay)
        
        while left < right:
            mid = (left + right) // 2
            
            if canmake(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], num_bouq: int, num_flowers: int) -> int:
        def canMake(day):
            i = 0
            num_adj = 0
            count = 0
            while i < len(bloomDay):
                if bloomDay[i] <= day:
                    num_adj += 1
                if num_adj == num_flowers:
                    count += 1
                    num_adj = 0
                if bloomDay[i] > day:
                    num_adj = 0
                    
                i += 1
                
            
            return count >= num_bouq
                    
        
        left = 1
        right = max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            if canMake(mid):
                right = mid
            else:
                left = mid + 1
                
        if canMake(left):
            return left
        else:
            return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        def fesible(mid):
            c,n,l = 0,0,[]
            b=[(i-mid) for i in bloomDay] 
            # print(b)
            for i in range(len(b)):
                # print(l)
                if b[i]<=0 and i!=(len(b)-1):
                    c+=1
                elif b[i]<=0 and i==(len(b)-1):
                    ##
                    c+=1
                    l.append(c)
                elif b[i]>0:
                    l.append(c)
                    c=0
            

            ss=0
            for i in l:
                ss+=i//k
            if ss>=m or m*k<=max(l):
                return True
            return False
        
        v=0
        left, right = min(bloomDay), max(bloomDay)+1
        while left<right:
            mid = left + (right-left)//2
            # print(mid)
            if fesible(mid):
                right=mid
                v=1
            else:
                left = mid +1
        if v==0:
            return -1
        return left
    
    
    
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        lo, hi = min(bloomDay), max(bloomDay)
        def check(d): # check if D days is good enough for m bouquets of k flowers
            cnt, start = 0, -1
            for i, val in enumerate(bloomDay):
                if val <= d and i - start >= k:
                    cnt += 1
                    start = i
                elif val > d:
                    start = i
            return cnt >= m
        
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        
        def isFeasible(days):
            
            bouquetsSoFar = 0
            flowersSoFar = 0
            
            for d in bloomDay:
                
                if d <= days:
                    flowersSoFar += 1
                    if flowersSoFar == k:
                        bouquetsSoFar += 1
                        flowersSoFar = 0
                        if bouquetsSoFar == m:
                            return True
                else:
                    flowersSoFar = 0
                
            return False
        
        if len(bloomDay) < m * k:
            return -1
        
        left, right = min(bloomDay), max(bloomDay)
        
        while left < right:
            
            mid = left + (right - left) // 2
            
            if isFeasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k: return -1
        l, r = 1, max(bloomDay)
        while l < r:
            p, curr, cnt = l + (r - l) // 2, 0, 0
            for x in bloomDay:
                curr = curr + 1 if x <= p else 0
                if curr >= k:
                    cnt, curr = cnt+1, curr - k
            if cnt < m: l = p+1
            else: r = p
        return l

'''
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        A = bloomDay
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left
'''
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m*k :return -1
        l, r = 1, max(bloomDay)
        while l < r:
            mid = l + (r - l) // 2
            temp = 0
            cnt = 0
            for n in bloomDay:
                temp = 0 if n > mid else temp + 1
                if temp >=k:
                    temp = 0
                    cnt+=1
                    if cnt==m:break
            if cnt == m : r= mid
            else: l = mid+1
        return l



class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            cnt, n = 0, 0
            for b in bloomDay:
                if b <= mid:
                    cnt += 1
                    if cnt == k:
                        n += 1
                        if n == m:
                            break
                        cnt = 0
                else:
                    cnt = 0
            if n == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        a=bloomDay
        if len(a)<m*k:return -1
        def ck(n,m,k):
            c=0
            b=0
            for x in a:
                if x<=n:
                    c+=1
                    if c==k:
                        b+=1
                        if b==m:return bool(1)
                        c=0
                else:c=0
            return bool(0)
        def bs(m,k):
            l,r=min(a),max(a)
            while l<r:
                mid=(l+r)//2
                if ck(mid,m,k):r=mid
                else:l=mid+1
            return l
        return bs(m,k)

class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq ==m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def isPossible(cap):
            bouquets = 0
            flowers = 0
            
           
            for flower in bloomDay:
                if flower <= cap:
                    flowers += 1
                else:
                    flowers = 0
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            if bouquets < m:
                return False
            else:
                return True
            
        
        left = 1
        right = max(bloomDay)
        if m*k > len(bloomDay):
            return -1
        while left < right:
            
            mid = left + (right-left)//2
            
            if isPossible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay)< m*k: return -1
        
        l, r= 1, max(bloomDay)
        while l< r:
            mid= (l+r)//2

            flow = bouq = 0
            for a in bloomDay:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    bouq += 1
                    flow = 0
                    if bouq == m:
                        break
            if bouq == m:
                r = mid
            else:
                l = mid + 1  
        return l
            


class Solution:
    def minDays(self, arr: List[int], m: int, k: int) -> int:
        def count(arr, x, k):
            out = 0
            count = 0
            for i in arr:
                if i <= x:
                    count += 1
                    if count == k:
                        out += 1
                        count = 0
                else:
                    count = 0

            return out
        
        if len(arr) < m*k:
            return -1
        res = -1
        bi = list(sorted(set(arr)))
        start = 0
        end = len(bi)-1
        while start <= end:
            mid = (start+end)//2
            if count(arr, bi[mid], k) >= m:
                res = bi[mid]
                end = mid - 1
            else:
                start = mid + 1

        return res

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        max_, min_ = max(bloomDay),min(bloomDay)
        
        def check(day):
            m_done = 0
            cont_count = 0
            for x in bloomDay:
                if x <= day:
                    cont_count +=1
                    if cont_count == k:
                        m_done +=1
                        cont_count = 0
                else:
                    cont_count = 0
            #print(day, m_done)
            if m_done < m:
                return False
            return True
        
        left = min_ - 1
        right = max_
        
        while left < right:
            mid = left + (right-left)//2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            mid = (l + r) // 2
            if not self.check(bloomDay, m, k, mid):
                l = mid + 1
            else:
                r = mid
        if self.check(bloomDay, m, k, l):
            return l
        return -1
    
    def check(self, bloomDay, m, k, day):
        cnt, consecutive = 0, 0
        for bd in bloomDay:
            if bd <= day:
                consecutive += 1
                if consecutive >= k:
                    cnt += 1
                    if cnt >= m:
                        return True
                    consecutive = 0
            else:
                consecutive = 0
        return False

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay): return -1
        low, high = min(bloomDay), max(bloomDay)
        while low < high:
            mid = (low + high) // 2
            flow = bouq = 0
            for bloom in bloomDay:
                if bloom > mid:
                    flow = 0
                else:
                    flow += 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: 
                        break
            if bouq == m:
                high = mid
            else:
                low = mid + 1
        return low
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay): return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in bloomDay:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay): return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for fl in bloomDay:
                if fl > mid:
                    flow = 0
                else:
                    flow += 1
                if flow >= k:
                    # enough adjacent flowers to make bouque
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq >= m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            flowers = 0
            bouquets = 0
            for day in bloomDay:
                flowers = flowers + 1 if day <= mid else 0
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            if bouquets < m:
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def minDays(self, bloomDay, m, k):

        #print (f\"bloomDay={bloomDay} m={m} k={k}\")

        def max_bouquets(bdays, k, days):
            count = 0
            cursum = 0
            for d in bdays:
                if (d > days ):
                    cursum = 0 # can't pick up that flower
                else:
                    cursum += 1
                    if cursum == k:
                        count += 1
                        cursum = 0
            #print(f\"bdays={bdays} -> can make {count} bouquets if waiting {days} days\")
            return count

        if m*k > len(bloomDay):
            return -1

        bDays = sorted(list(set(sorted(bloomDay)[m*k-1:])))
        left = 0
        right = len(bDays)
        minDays = -1
        while left<right:
            mid = left + int((right-left)/2)
            #print(f\"left={left} mid={mid} right={right}\")
            val = bDays[mid]
            if max_bouquets(bloomDay,k, val) >= m:
                minDays = val
                right = mid
            else:
                left = mid+1
        return minDays
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if len(bloomDay) < m * k:
            return -1
        
        b = min(bloomDay)
        e = max(bloomDay)
        
        def check_day(day):
            flowers = 0
            bouquets = 0
            for d in bloomDay:
                if d > day:
                    flowers = 0
                else:
                    flowers += 1
                    if flowers >= k:
                        bouquets += 1
                        flowers = 0
                        if bouquets >= m:
                            return True
            return False
        
        while e>=b:
            mid = (b+e)//2
            
            if check_day(mid):
                e = mid - 1
            else:
                b = mid + 1
                
        return b

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k>len(bloomDay):
            return -1
        def can_make(day):
            bouquet,count = 0,0
            for i in bloomDay:
                if day>=i:
                    count += 1
                else:
                    count = 0
                if count==k:
                    bouquet += 1
                    count = 0
                    if bouquet==m:
                        return True
            return False
        
        left,right = min(bloomDay),max(bloomDay)
        while left<right:
            mid = left + (right-left)//2
            if can_make(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay, m, k):
        start, end = 1, max(bloomDay)
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.check(mid, bloomDay, m, k):
                end = mid
            else:
                start = mid
        if self.check(start, bloomDay, m, k):
            return start
        if self.check(end, bloomDay, m, k):
            return end
        return -1
    
    def check(self, days, bloomDay, m, k):
        cnt = 0
        res = 0
        for d in bloomDay:
            if d <= days:
                cnt += 1
            else:
                cnt = 0
            if cnt == k:
                res += 1
                cnt = 0
        return res >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if not bloomDay :return -1
        if k * m > len(bloomDay): return -1

        def check(cur):
            res = 0
            curk = 0
            for item in bloomDay:
                if item <= cur:
                    curk += 1
                    if curk == k:
                        res+=1
                        curk = 0
                else:
                    curk = 0
            if res < m: return False
            return True

        b = min(bloomDay)
        e = max(bloomDay) 
        rt = 0
        #n2
        while b <= e:
            
            mid = b + (e-b)//2
            if check(mid):
                e = mid-1
            else:
                b = mid +1
        return b
            
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        #arr = [abs difference prev and cur]
#         # for idx, val in enumerate(bloomDay):
#         h = defaultdict(list)
#         for idx, val in enumerate(bloomDay):
            
#             dif = abs(bloomday[idx+1] - val)
#             h[dif].append((idx, idx+1))
            
        
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        return rt


class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A):
            return -1
        
        def isit(d):
            c = b = 0
            for a in A:
                c = 0 if a>d else c+1
                if c==k:
                    c=0
                    b+=1
                    if b==m:
                        return 1
            return 0

        l = 1
        r = max(A)
        while l < r:
            mid = (l+r)//2
            if isit(mid):
                r = mid
            else:
                l = mid + 1
        return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        A = bloomDay
        if m * k > len(A): return -1
        left, right = 1, max(A)
        while left < right:
            mid = (left + right) // 2
            flow = bouq = 0
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left
            


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

        bloom_day_flowers = {}
        for i, day in enumerate(bloomDay):
            bloom_day_flowers.setdefault(day, []).append(i)
            
        days = sorted(bloom_day_flowers.keys())
        
        segments = {}
        total_b = 0

        for day in days:
            for flower in bloom_day_flowers[day]:
                assert flower not in segments
                
                lower_ext, upper_ext = False, False
                lower_rm, upper_rm = 0, 0
                new_seg = None
                
                # check lower interval
                if flower - 1 in segments:
                    seg = segments[flower - 1]
                    seg[1] = flower
                    segments[flower] = seg
                    lower_rm = seg[1] - seg[0]
                    if lower_rm > 1:
                        del segments[flower - 1]
                    new_seg = seg
                    lower_ext = True
                
                # check upper interval
                if flower + 1 in segments:
                    if flower in segments:
                        # merge segments
                        lower_seg = segments[flower]
                        upper_seg = segments[flower + 1]
                        upper_rm = upper_seg[1] - upper_seg[0] + 1
                        
                        new_end = upper_seg[1]
                        lower_seg[1] = new_end
                        del segments[flower + 1]
                        del segments[flower]
                        segments[new_end] = lower_seg
                        new_set = lower_seg
                    else:
                        seg = segments[flower + 1]
                        seg[0] = flower
                        segments[flower] = seg
                        upper_rm = seg[1] - seg[0]
                        if upper_rm > 1:
                            del segments[flower + 1]
                        new_seg = seg
                    upper_ext = True
                
                if not (lower_ext or upper_ext):
                    seg = [flower, flower]
                    segments[flower] = seg
                    new_seg = seg
                
                total_b -= lower_rm // k + upper_rm // k
                total_b += (new_seg[1] - new_seg[0] + 1) // k
                    
                
                # print(day, total_b, segments)
                if total_b >= m:
                    return day
                
        return -1


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay): return -1
        
        M = max(bloomDay)
        lo, hi= 0,M
        
        def works(h):
            curr = 0
            bou = 0
            for b in bloomDay:
                if b<=h:
                    curr+=1
                    if curr==k:
                        bou+=1
                        curr=0
                    if bou==m:
                        return True
                else:
                    curr=0
        
        while hi-lo>1:
            h = (hi+lo)//2
            if works(h):
                hi=h
            else:
                lo=h
        
        return hi     

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def can(days):
            res = 0
            count = 0
            for a in bloomDay:
                if a <= days:
                    count += 1
                else:
                    count = 0
                if count == k:
                    count = 0
                    res += 1
            return res >= m
            
        l, r = 1, max(bloomDay)
        while l < r:
            mid = (l + r)//2
            if can(mid):
                r = mid
            else:
                l = mid + 1
        if can(l):
            return l
        return -1


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):   #要形成至少需要的花朵数
            return -1
        l, r = 1, max(bloomDay)
        while l < r:
            mid = (l+r)//2
            flow = bouq = 0
            for a in bloomDay:
                if a > mid:
                    flow=0
                else:
                    flow+=1
                if flow== k:
                    flow = 0
                    bouq += 1
            if bouq>=m:
                r = mid
            else:
                l = mid + 1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def canMake(bloomDay, m, k, day):         
            cur, cnt = 0, 0
            for i in range(len(bloomDay)):
                if bloomDay[i] <= day:
                    cur += 1
                    if cur == k:
                        cnt += 1
                        cur = 0
                        if cnt == m:
                            return True
                else:
                    cur = 0
            return False
        if m*k > len(bloomDay):
            return -1
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if not canMake(bloomDay, m, k, mid):
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k: return -1
        l, r = 1, max(bloomDay)
        while l < r:
            p, curr, cnt = l + (r - l) // 2, 0, 0
            for x in bloomDay:
                curr = curr + 1 if x <= p else 0
                if curr == k:
                    cnt, curr = cnt+1, 0
                if cnt == m: break
            if cnt < m: l = p+1
            else: r = p
        return l

class Solution:
    def minDays(self, bloom_day: List[int], m: int, k: int) -> int:
        
        def bouquets_made(day):
            total = adjacent = 0
            for d in bloom_day:
                if d <= day:
                    adjacent += 1
                else:
                    adjacent = 0
            
                if adjacent == k:
                    total += 1
                    adjacent = 0
                
            return total
        
        
        min_days = -1
        lo, hi = 1, max(bloom_day)
        while lo <= hi:
            mid = (lo + hi) // 2
            if bouquets_made(mid) >= m:
                min_days = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        return min_days


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m*k:
            return -1
        
        l, r = min(bloomDay), max(bloomDay)
        while l < r:
            mid = (l+r)//2
            temp = self.bouquets(mid, bloomDay, k, m)
            if temp:
                r = mid
            else:
                l = mid+1
        return l
            
            
    
    def bouquets(self, day, bloomDay, k, m):
        c = 0
        contDays = 0
        for i in range(len(bloomDay)):
            if bloomDay[i] > day:
                contDays = 0
                continue

            contDays += 1
            if contDays == k:
                c += 1
                contDays = 0
        return c >= m


class Solution:
    def minDays(self, b: List[int], m: int, k: int) -> int:
        if m*k > len(b):
            return -1
        l,r = min(b), max(b)
        def possible(days):
            bonquets, flowers = 0, 0
            for bloom in b:
                if bloom > days:
                    flowers = 0
                else:
                    flowers += 1
                if flowers == k:
                    flowers = 0
                    bonquets += 1
            return bonquets >= m
            
        while l<r:
            mi = (l+r)//2
            
            if possible(mi):
                r = mi
            else:
                l = mi+1
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if not bloomDay :return -1
        if k * m > len(bloomDay): return -1

        def check(cur):
            res = 0
            curk = 0
            for item in bloomDay:
                if item <= cur:
                    curk += 1
                    if curk == k:
                        res+=1
                        curk = 0
                else:
                    curk = 0
            if res < m: return False
            return True

        b = min(bloomDay)
        e = max(bloomDay) 
        rt = 0
        #n2
        while b < e:
            
            mid = b + (e-b)//2
            if check(mid):
                e = mid
            else:
                b = mid +1
        return b
            
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        #arr = [abs difference prev and cur]
#         # for idx, val in enumerate(bloomDay):
#         h = defaultdict(list)
#         for idx, val in enumerate(bloomDay):
            
#             dif = abs(bloomday[idx+1] - val)
#             h[dif].append((idx, idx+1))
            
        
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        return rt


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        curr = 0
        left = len(bloomDay)*[0]
        right = len(bloomDay)*[0]
        days = defaultdict(list)
        for i in range(len(bloomDay)):
            days[bloomDay[i]].append(i)
        sorted_days = sorted(days)
        for i in sorted_days:
            for x in days[i]:
                right[x] = 1
                left[x] = 1
                if x < len(bloomDay)-1:
                    right[x] += right[x+1]
                if x > 0:
                    left[x] += left[x-1]
                if ((left[x]-1)%k + (right[x]-1)%k + 1) >= k:
                    curr += 1
                    if curr == m:
                        return i
                right[x-left[x]+1] = left[x] + right[x] - 1
                left[x+right[x]-1] = left[x] + right[x] - 1
        return -1

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(largest):
            cur_len, made = 0, 0
            for bloom in bloomDay:
                if bloom > largest:
                    cur_len = 0
                    continue
                cur_len += 1
                if cur_len == k:
                    made += 1
                    cur_len = 0
                if made == m:
                    return True
            return False
        
        if len(bloomDay) < k*m:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left+right) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m*k:
            return -1
        left, right = min(bloomDay), max(bloomDay)
        while left <= right:
            mid = left + (right-left)//2
            if self.feasible(mid, m, k, bloomDay): # need min number of days
                right = mid -1
            else:
                left = mid + 1
        return right + 1

    def feasible(self, mid, m, k, bloomDay):
        # all available flowers after mid days of waiting
        # check if it's possible to make m bouquets with the available flowers 
        # need m, k adjacent flowers
        adj_flower = 0
        bouquet_num = 0
        for d in bloomDay:
            if d <= mid:
                adj_flower +=1
                if adj_flower ==k:
                    bouquet_num +=1
                    adj_flower = 0
            else:
                adj_flower = 0
        return bouquet_num >= m

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1

        def feasible(day):  # check whether it is possible to arrange m banquet on this day.
            banquet = 0
            streak = 0
            for d in bloomDay:
                if d > day:  # available
                    streak = 0
                else:
                    streak += 1
                    if streak == k:  # enough for a banquet
                        banquet += 1
                        streak = 0
                    if banquet == m:  # enough banquet
                        return True
            return False

        low, high = min(bloomDay), max(bloomDay)
        while low < high:
            mid = (low + high) // 2
            if feasible(mid):
                high = mid
            else:
                low = mid + 1
        return low

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if  m*k > len(bloomDay)+1:
            return -1
        pos = False
        
        
        def possible(mid):
            a , curr = 0,0
            for bloom in bloomDay:
                if bloom > mid:
                    a = 0
                else:
                    a +=1
                    if a == k:
                        a = 0
                        curr += 1
            if curr >= m:
                return True
            else:
                return False

       
        left, right=min(bloomDay),max(bloomDay)
        while(left<right):
            mid = left +(right-left)//2
            if possible(mid):
                pos = True
                right = mid
            else:
                left = mid + 1
        
        if possible(left):
            return left
    
        else:
            return -1

from itertools import groupby

class Solution:
    def minDays(self, b: List[int], m: int, k: int) -> int:
        
        def is_possible(arr, min_day):
            after_days = [1 if min_day >= d else 0 for d in b]

            cont_days = sum([len(list(g)) // k for num, g in groupby(after_days) if num == 1])
            return cont_days >= m



        if m * k > len(b):
            print(-1)
            return -1

        else:
            left, right = min(b), max(b)

            while left < right:
                mid = left + (right - left) // 2

                if is_possible(b, mid):
                    right = mid
                else:
                    left = mid + 1

            print(left)
            return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        if k*m > len(bloomDay):
            return -1
        
        unique_bloom_days = sorted(set(bloomDay))

        
        
        
        lo = 0
        hi = len(unique_bloom_days)-1
        
        if hi == 0:
            return unique_bloom_days[0]
        
        while True:
            curr_idx = int((lo+hi)/2)
            if curr_idx == lo:
                idx = curr_idx
            curr_day = unique_bloom_days[curr_idx]
            # check if the condition is satisfiable
            bouquet = 0
            curr = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] <= curr_day:
                    curr += 1
                    if curr >= k:
                        bouquet += 1
                        curr = 0
                else:
                    curr = 0
            
            if bouquet < m:  # not enough
                if curr_idx == lo:
                    idx = lo+1
                    break
                else:
                    lo = curr_idx
            else:  # enough
                hi = curr_idx
                if hi == lo:
                    idx = hi
                    break
        return unique_bloom_days[idx]

class Solution:
    def minDays(self, A: List[int], m: int, k: int) -> int:
        if m * k > len(A): return -1
        
        left, right = 1, max(A)
        
        while left < right:
            mid = (left + right) >> 1
            flow = bouq = 0
            
            for a in A:
                flow = 0 if a > mid else flow + 1
                if flow >= k:
                    flow = 0
                    bouq += 1
                    if bouq == m: break
            if bouq == m:
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if bloomDay == [] or m * k == 0 or len(bloomDay) < m * k:
            return -1
        left, right = 1, max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if self.getPossibleBouquetNum(bloomDay, k, mid) >= m:
                right = mid
            else:
                left = mid + 1
        return left
    
    def getPossibleBouquetNum(self, bloomDay: List[int], k: int, day_threshold: int) -> int:
        bloom_count = 0
        bouquet_count = 0
        for day in bloomDay:
            if day <= day_threshold:
                bloom_count += 1
            else:
                bouquet_count += bloom_count // k
                bloom_count = 0
        bouquet_count += bloom_count // k
        return bouquet_count

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def bouqets(d):
            res, c = 0, 0
            for n in bloomDay:
                c = 0 if n > d else c + 1
                if c == k:
                    res, c = res + 1, 0
            return res
            
        days = sorted(set(bloomDay))
        lo, hi = 0, len(days)-1
        while lo < hi:
            mid = (lo + hi) // 2
            if bouqets(days[mid]) < m:
                lo = mid + 1
            else:
                hi = mid
        return days[hi] if days[hi] >= m else -1


class Solution:
    def make_bouquets(self, A, day, k):
        cnt, consec = 0, 0
        for i in A:
            if day >= i:
                consec += 1
            else:
                consec = 0
            if consec == k:
                cnt += 1
                consec = 0
        return cnt
    
    def minDays(self, A, m, k):
        l, r = min(A), max(A)
        print(f'{l=} | {r=}')
        while r > l:
            mid = (l+r) // 2
            if self.make_bouquets(A, mid, k) >= m:
                r = mid
            else:
                l = mid + 1
        print(f'{l=} | {r=}')
        if self.make_bouquets(A, l, k) >= m:
            return l
        else: return -1

        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if (len(bloomDay) < m * k):
            return -1
        
        sorted_bloomDay = sorted(set(bloomDay))
        left = 1
        right = len(sorted_bloomDay)
        ret = -1

        
        while (left <= right):
            middle = (left + right) // 2 - 1
            bouquets_left = m
            flowers_left = k 
            search_right = True
            
            
            for i in range(len(bloomDay)):
                if (bloomDay[i] <= sorted_bloomDay[middle]):
                    flowers_left -= 1
                    
                    
                    if (flowers_left == 0):
                        bouquets_left -= 1
                        
                        
                        if (bouquets_left == 0):
                            ret = sorted_bloomDay[middle]
                            search_right = False
                            break
                        else:
                            flowers_left = k
                else:
                    flowers_left = k
                    
            
            if (search_right):
                left = middle + 2
            else:
                right = middle
                
        return ret

class Solution:
    def is_good(self, day):
        bouqet_count = 0
        cont_count = 0
        for d in self.bloomDay:
            if d <= day:
                cont_count += 1
            else:
                bouqet_count += cont_count // self.k
                cont_count = 0
        bouqet_count += cont_count // self.k
        return bouqet_count >= self.m
        
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        self.bloomDay = bloomDay
        self.m = m
        self.k = k
        
        if m * k > len(bloomDay):
            return -1
        start = 1
        end = 10**9
        
        
        while start != end:
            middle = (start + end) // 2
            if self.is_good(middle):
                end = middle
            else:
                start = middle + 1
        
        return start

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        b=bloomDay
        if m*k>len(b):
            return -1
        else:
            def posb(c)->bool:
                p=0
                l=0
                for i in range(len(b)):
                    if b[i]>c:
                        l=0
                    else:
                        l+=1
                        if l==k:
                            p+=1
                            l=0
                        

                #print(p,c)

                return p>=m
            l,r=min(b),max(b)
            while l<r:
                mid=l+(r-l)//2
                if posb(mid):
                    r=mid
                else:
                    l=mid+1
            return l


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # minDay
        # we need k consecutive elems in bloomDay list where all those elems <= minDay
        # we need m such groups
        
        # minimum possible val is min val in the list
        # maxmimum possible val is max val in the list
        # impossible case: m * k > list size
        
        if m * k > len(bloomDay):
            return -1
        
        def condition(minDay):
            numB = m
            curF = 0
            for day in bloomDay:
                if day <= minDay:
                    curF += 1
                    if curF == k:
                        numB -= 1
                        curF = 0
                    if numB == 0:
                        break
                else:
                    curF = 0
            return numB == 0
        
        l = min(bloomDay)
        r = max(bloomDay)
        # possible = 0
        while l < r:
            mid = l + (r - l) // 2
            if condition(mid):
                r = mid
            else:
                l = mid + 1
       
        return l

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay): return -1
        else: 
            left, right = 0, max(bloomDay)
            while left < right:
                mid = (left + right) // 2
                flow, bq = 0,0
                for d in bloomDay:
                    if d > mid:
                        flow = 0
                    else:
                        flow += 1
                    if flow == k:
                        bq += 1
                        flow = 0
                    if bq == m:
                        break
                if bq == m:
                    right = mid
                else:
                    left = mid + 1
            return left

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        vals = list(set(bloomDay))
        vals.sort()
        
        def invalid(threshold):
            cur = 0
            bouquets = 0
            for x in bloomDay:
                if x <= threshold:
                    cur += 1
                else:
                    bouquets += cur // k
                    cur = 0
            bouquets += cur // k
            return bouquets < m
        
        left, right = 0, len(vals) - 1
        while left <= right:
            mid = (left + right) // 2
            # print(left, right, mid)
            if invalid(vals[mid]):
                left = mid + 1
            else:
                right = mid - 1
        return vals[left]

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(bloomDay, day, m, k):
            count = 0
            for flower in bloomDay:
                if flower <= day:
                    count += 1
                    if count == k:
                        m -= 1
                        count = 0
                    if m == 0:
                        return True
                else:
                    count = 0
            return False
        
        start = min(bloomDay)
        end = max(bloomDay)
        res = -1 
    
        while start <= end:
            center = start + (end - start) // 2
            if check(bloomDay, center, m, k):
                res = center
                end = center - 1
            else:
                start = center + 1
        
        return res


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def isValid(val):
            count = 0
            tmp = 0
            for i in range(len(bloomDay)):
                if bloomDay[i] <= val:
                    tmp += 1
                    if tmp == k:
                        count += 1
                        if count == m:
                            return True
                        tmp = 0
                else:
                    tmp = 0
            return False
        
        
        ls = len(bloomDay)
        if m * k > ls:
            return -1
        
        l, r = min(bloomDay), max(bloomDay)
        
        while l < r:
            mid = (l + r) // 2
            if isValid(mid):
                r = mid
            else:
                l = mid + 1
                
        return l
        
        


class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # 花的总数>=m*k则一定能完成
        n = len(bloomDay)
        if n < m * k:
            return -1
        # 搜索所有可能的天数, 如果第x天无法满足条件, x-1, x-2...也无法满足条件
        # 二分查找 满足条件最小k的模板
        lo = 1
        hi = max(bloomDay)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.can_make(mid, bloomDay, m, k):
                hi = mid
            else:
                lo = mid + 1
        return lo
    
    def can_make(self, day, bloomDay, m, k):
        cnt = 0
        for d in bloomDay:
            if d <= day:
                cnt += 1
            else:
                cnt = 0
            if cnt == k:
                m -= 1
                cnt = 0
            if m == 0:
                return True
        return m == 0


class Solution:
    def checkDay(self,day,bloomDay,m,k)->bool:
        y,count=0,0
        for i in range(len(bloomDay)):
            if bloomDay[i] <= day:
                #bloomed.append(1)
                y+=1
            else:
                #bloomed.append(0)
                y=0
            if y==k:
                count+=1
                y=0
            if count==m:
                return True
        return False
    
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        '''
        bloomDay: Flower garden, elements are # of days required for that flower to bloom
        m: # of bouquets needed
        k: # of adjacent flowers needed in each bouquet
        First, check to see if mk>len(bloomDay). If so return -1
        Then, see how many days needed until mk flowers have bloomed
            Check to see if they are adjacent
            if so return days
            else maybe check how many adjacents are needed, or go to the next day
        
        '''
        #bloomDay,m,k = [7,7,7,7,12,7,7],2,3
        
        FN=m*k # (Flowers Needed)
        if FN > len(bloomDay):
            return -1
        
        
        # After x days, is it possible to create m bouquets?
        
        
        bloomed=sorted(bloomDay)
        lastWorking,count,start,stop=-1,0,0,len(bloomed)
        #print(bloomed)
        half=stop//2
        #day=bloomed[half]
        while(start<=half<stop):
            day=bloomed[half]
            #print('Half: ',half,', Day: ',day,' || Bounds: ',start,', ',stop)
            
            # If current day works, check previous day
            if self.checkDay(day,bloomDay,m,k):
                #print('Day:  ',day,' works')
                lastWorking,stop=day,half
            # Otherwise check half of new bounds
            else:
                start=half+1
            half=(start+stop)//2
            
        return lastWorking

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
        
        def feasible(days,m,k):
            flowers =0
            bouq =0
            for item in bloomDay:
                if item <= days:
                    flowers +=1
                else:
                    flowers =0
                if flowers >=k:
                    bouq +=1
                    flowers =0
                    if bouq == m:
                        return True
            return False
        
        left = min(bloomDay) # min number of days
        right = max(bloomDay)# maximum number of days
        while left < right:
            mid = left + (right-left) //2
            if feasible(mid,m,k):
                right = mid
            else:
                left = mid +1
        return left


class Solution:
    def minDays(self, bloomDay: List[int], M: int, K: int) -> int:
        if len(bloomDay) < M * K : return -1
        def condition(day) -> bool:
            m, k = 0, 0
            for bd in bloomDay:
                if bd <= day : k += 1
                else : k = 0
                if k >= K : 
                    m += 1
                    k = 0
                if m >= M : return True
            return False

        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left        

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n//k < m:
            return -1
        
        left = min(bloomDay)
        right = max(bloomDay)
        
        while left < right:
            mid = (left + right)//2
            numBouqets = 0
            count = 0
            for i in range(n):
                if bloomDay[i]<=mid:
                    count += 1
                else:
                    count = 0
                if count == k:
                    count = 0
                    numBouqets += 1
            # print(left, mid, right, numBouqets)
            if numBouqets >= m:
                right = mid
            else:
                left = mid+1
        return left