To make one bouquet we need K adjacent flowers from the garden. Here the garden consists of N different flowers, the ith flower will bloom in the bloomDay[i]. Each flower can be used inside only one bouquets. We have to find the minimum number of days need to wait to make M bouquets from the garden. If we cannot make m bouquets, then return -1.
The first line of input contains two integers M and K.
The second line contains N space-separated integers of bloomDay[i] array.
Example 1:
Input:
M = 2, K = 3
bloomDay = [5, 5, 5, 5, 10, 5, 5]
Output:
10
Explanation:
As we need 2 (M = 2) bouquets and each should have 3 flowers,
After day 5: [x, x, x, x, _, x, x], we can make one bouquet of
the first three flowers that bloomed, but cannot make another bouquet.
After day 10: [x, x, x, x, x, x, x], Now we can make two bouquets,
taking 3 adjacent flowers in one bouquet.
Example 2:
Input: 
M = 3, K = 2
bloomDay = [1, 10, 3, 10, 2]
Output: 
-1
Explanation:
As 3 bouquets each having 2 flowers are needed, that means we need 6 flowers. 
But there are only 5 flowers so it is impossible to get the needed bouquets
therefore -1 will be returned.
Your Task:
Complete the function int solve(), which takes integer M, K, and a list of N integers as input and returns the  minimum number of days needed to wait to be able to make M bouquets from the garden.
 
Expected Time Complexity: O(N.log(maxVal)), where maxVal = max(bloomDay)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= M <= 10^{5}
1 <= K <= N
1 <= bloomDay[i] <= 10^{9}

Difficulty: MEDIUM
Expected Time Complexity: O(N.log(maxVal)), where maxVal = max(bloomDay)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def solve(self, M, K, bloomDay):

        # Code here

Solutions:
class Solution:

	def solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		l = min(bloomDay)
		r = max(bloomDay)
		while l <= r:
			mid = (l + r) // 2
			count = 0
			bq = 0
			for i in range(len(bloomDay)):
				if count < K and bloomDay[i] > mid:
					count = 0
				if bloomDay[i] <= mid:
					count = count + 1
				if count == K:
					bq = bq + 1
					count = 0
			if bq == M:
				ans = mid
				r = mid - 1
			elif bq < M:
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def ok(self, m, k, v, b):
		curr = 0
		for a in b:
			if v >= a:
				curr += 1
				if curr == k:
					m -= 1
					curr = 0
			else:
				curr = 0
		return m <= 0

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		(lo, hi) = (min(bloomDay), max(bloomDay))
		ans = -1
		while lo <= hi:
			mi = (lo + hi) // 2
			if self.ok(M, K, mi, bloomDay):
				ans = mi
				hi = mi - 1
			else:
				lo = mi + 1
		return ans


class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		start = min(bloomDay)
		end = max(bloomDay)
		while start <= end:
			mid = (start + end) // 2
			bouquets = 0
			adjacent = 0
			for day in bloomDay:
				if day > mid:
					adjacent = 0
				else:
					adjacent += 1
					if adjacent == K:
						bouquets += 1
						adjacent = 0
				if bouquets >= M:
					break
			if bouquets >= M:
				end = mid - 1
			else:
				start = mid + 1
		return start


class Solution:

	def solve(self, M, K, bloomDay):
		l = 0
		r = max(bloomDay)
		if len(bloomDay) < M * K:
			return -1
		while l < r:
			mid = (l + r) // 2
			total = 0
			m = 0
			for i in range(len(bloomDay)):
				if bloomDay[i] <= mid:
					total += 1
				else:
					total = 0
				if total == K:
					m += 1
					total = 0
			if m >= M:
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		l = 1
		r = max(bloomDay)
		mid = None
		res = -1
		while l <= r:
			mid = (l + r) // 2
			s = 0
			m = 0
			for i in bloomDay:
				if i <= mid:
					s += 1
				else:
					s = 0
				if s == K:
					m += 1
					s = 0
			if m >= M:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		elif M * K == len(bloomDay):
			return max(bloomDay)
		else:
			low = 1
			high = max(bloomDay)
			res = -1
			while low <= high:
				mid = low + (high - low) // 2
				sum = 0
				m = 0
				for i in range(len(bloomDay)):
					if bloomDay[i] <= mid:
						sum += 1
					else:
						sum = 0
					if sum == K:
						m += 1
						sum = 0
				if m >= M:
					res = mid
					high = mid - 1
				else:
					low = mid + 1
			return res


class Solution:

	def solve(self, m, k, bloomday):
		if m * k > len(bloomday):
			return -1
		l = 1
		r = max(bloomday)
		mid = 0
		while l <= r:
			mid = (l + r) // 2
			g = 0
			boq = 0
			for i in range(len(bloomday)):
				if bloomday[i] <= mid:
					g += 1
					if g == k:
						boq += 1
						g = 0
				else:
					g = 0
			if m <= boq:
				r = mid - 1
			else:
				l = mid + 1
		return l


from typing import List

class Solution:

	def solve(self, M: int, K: int, bloomDay: List[int]) -> int:
		if len(bloomDay) < M * K:
			return -1
		low = 0
		high = max(bloomDay)
		res = -1
		while low <= high:
			mid = low + (high - low) // 2
			sum = 0
			m = 0
			for i in range(len(bloomDay)):
				if bloomDay[i] <= mid:
					sum += 1
				else:
					sum = 0
				if sum == K:
					m += 1
					sum = 0
			if m >= M:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def solve(self, m, k, bloomDay):
		if k * m > len(bloomDay):
			return -1
		ans = -1
		low = 1
		high = max(bloomDay)
		while low <= high:
			mid = low + high >> 1
			tot = 0
			cnt = 0
			for day in bloomDay:
				if day <= mid:
					cnt += 1
					if k == cnt:
						tot += 1
						cnt = 0
				else:
					cnt = 0
			if tot >= m:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def solve(self, M, K, bloomDay):
		m = M
		k = K
		lo = 1
		hi = max(bloomDay)
		if len(bloomDay) < m * k:
			return -1
		ans = 2 ** 31

		def possible(mid):
			temp = 0
			b = 0
			for i in range(len(bloomDay)):
				if bloomDay[i] <= mid:
					temp += 1
					if temp >= k:
						b += 1
						temp = 0
				else:
					temp = 0
			if b >= m:
				return True
			return False
		while lo <= hi:
			mid = (lo + hi) // 2
			if possible(mid):
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		if ans == 2 ** 31:
			return -1
		else:
			return ans


class Solution:

	def getNumberOfBouquets(self, K, bloomDay, curr_day):
		arr = []
		for elem in bloomDay:
			if elem > curr_day:
				arr.append(0)
			else:
				arr.append(1)
		count = 0
		sum = 0
		for i in range(len(arr)):
			if arr[i] == 0:
				sum = 0
			else:
				sum += arr[i]
				if sum == K:
					sum = 0
					count += 1
		return count

	def solve(self, M, K, bloomDay):
		N = len(bloomDay)
		if M * K > N:
			return -1
		elif M * K == N:
			return max(bloomDay)
		else:
			(l, r, curr_day) = (0, max(bloomDay), 0)
			min_days_to_m = r
			while l <= r:
				curr_day = (l + r) // 2
				number_of_bouquets = self.getNumberOfBouquets(K, bloomDay, curr_day)
				if number_of_bouquets < M:
					l = curr_day + 1
				else:
					min_days_to_m = min(min_days_to_m, curr_day)
					r = curr_day - 1
			return min_days_to_m


class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1

		def possible(days):
			bouquets = 0
			flowers = 0
			for bloom in bloomDay:
				if bloom > days:
					flowers = 0
				else:
					flowers += 1
					if flowers == K:
						bouquets += 1
						flowers = 0
				if bouquets == M:
					return True
			return False
		low = 1
		high = max(bloomDay)
		while low < high:
			mid = (low + high) // 2
			if possible(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def max_min(self, bloomDay, n):
		maxi = -float('inf')
		mini = float('inf')
		for i in range(n):
			maxi = max(maxi, bloomDay[i])
			mini = min(mini, bloomDay[i])
		return (maxi, mini)

	def find_boq(self, K, bloomDay, n, mid):
		temp = 0
		boq = 0
		for i in range(n):
			if bloomDay[i] <= mid:
				temp += 1
			else:
				temp = 0
			if temp == K:
				boq += 1
				temp = 0
		return boq

	def solve(self, M, K, bloomDay):
		n = len(bloomDay)
		if n < M * K:
			return -1
		elif n == M * K:
			return max(bloomDay)
		else:
			ans = float('inf')
			(high, low) = self.max_min(bloomDay, n)
			while low <= high:
				mid = (low + high) // 2
				boq = self.find_boq(K, bloomDay, n, mid)
				if boq < M:
					low = mid + 1
				else:
					ans = mid
					high = mid - 1
			return ans


class Solution:

	def solve(self, M, K, bloomDay):

		def bouquets(days):
			count = 0
			f = 0
			for d in bloomDay:
				if d <= days:
					f += 1
					if f >= K:
						count += 1
						f = 0
						if count >= M:
							return 1
				else:
					f = 0
			return 0
		if len(bloomDay) < M * K:
			return -1
		low = min(bloomDay)
		high = max(bloomDay)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if bouquets(mid):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def solve(self, M, K, arr):
		if len(arr) < M * K:
			return -1
		(low, high) = (1, max(arr))
		while low < high:
			mid = (low + high) // 2
			flow = bouq = 0
			for a in arr:
				flow = 0 if mid < a 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 solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1

		def approve(days):
			count = 0
			num = 0
			for day in bloomDay:
				if day <= days:
					count += 1
				else:
					count = 0
				if count == K:
					num += 1
					count = 0
			return num >= M
		l = min(bloomDay)
		r = max(bloomDay)
		res = -1
		while l <= r:
			mid = l + (r - l) // 2
			if approve(mid):
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, m, k, bloomDay):

		def canBoquetsForm(mid):
			total = 0
			target = 0
			for i in bloomDay:
				if i > mid:
					target = 0
				else:
					target += 1
					if target == k:
						total += 1
						target = 0
					if total >= m:
						break
			return total
		l = 1
		h = max(bloomDay)
		if m * k > len(bloomDay):
			return -1
		while l <= h:
			mid = (l + h) // 2
			res = canBoquetsForm(mid)
			if res < m:
				l = mid + 1
			else:
				h = mid - 1
		return l


class Solution:

	def solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		elif len(bloomDay) == M * K:
			return max(bloomDay)
		else:
			(left, right) = (1, max(bloomDay))
			while left < right:
				mid = (left + right) // 2
				bouquets = 0
				flowers = 0
				for i in bloomDay:
					if i > mid:
						flowers = 0
					else:
						flowers += 1
						if flowers == K:
							bouquets += 1
							flowers = 0
					if bouquets == M:
						break
				if bouquets < M:
					left = mid + 1
				else:
					right = mid
			return left


class Solution:

	def solve(self, m, k, bloomDay):
		n = len(bloomDay)
		if m * k > n:
			return -1

		def possible(x):
			count = 0
			bouquets = 0
			for d in bloomDay:
				if d <= x:
					count += 1
					if count == k:
						bouquets += 1
						count = 0
				else:
					count = 0
			return bouquets >= m
		(left, right) = (0, max(bloomDay) + 1)
		while left < right:
			mid = (left + right) // 2
			if possible(mid):
				right = mid
			else:
				left = mid + 1
		if possible(left):
			return left
		else:
			return left + 1


def isBloomed(arr, mid, m, k):
	n = len(arr)
	consec = 0
	total = 0
	for i in range(n):
		if arr[i] <= mid:
			total += 1
		else:
			if total >= k:
				consec += 1
			total = 0
		if total >= k:
			consec += 1
			total = 0
	if total >= k:
		consec += 1
		total = 0
	return consec >= m

class Solution:

	def solve(self, m, k, bloomDay):
		low = min(bloomDay)
		high = max(bloomDay)
		flowers = m * k
		if flowers > len(bloomDay):
			return -1
		while low <= high:
			mid = low + (high - low) // 2
			if isBloomed(bloomDay, mid, m, k):
				high = mid - 1
			else:
				low = mid + 1
		return low


class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		l = 0
		h = max(bloomDay)
		res = -1
		while l <= h:
			mid = l + int((h - l) // 2)
			s = 0
			m = 0
			for i in range(len(bloomDay)):
				if bloomDay[i] <= mid:
					s += 1
				else:
					s = 0
				if s == K:
					m += 1
					s = 0
			if m >= M:
				res = mid
				h = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, m, k, bloomDay):
		n = len(bloomDay)
		if m * k > n:
			return -1
		b_min = 9999999999
		b_max = -1
		for el in bloomDay:
			if el > b_max:
				b_max = el
			if el < b_min:
				b_min = el
		ans = 9999999999
		while b_min <= b_max:
			mid = (b_min + b_max) // 2
			par_ans = 0
			cnt = 0
			for el in bloomDay:
				if el <= mid:
					cnt += 1
				else:
					par_ans += cnt // k
					cnt = 0
			par_ans += cnt // k
			if par_ans >= m:
				ans = min(ans, mid)
				b_max = mid - 1
			else:
				b_min = mid + 1
		return ans


class Solution:

	def solve(self, M, K, bloomDay):
		N = len(bloomDay)
		if M * K > N:
			return -1
		ans = max(bloomDay)
		low = 1
		high = ans
		while low <= high:
			mid = (low + high) // 2
			count = 0
			temp = 0
			for i in range(N):
				if bloomDay[i] <= mid:
					temp += 1
				else:
					count += temp // K
					temp = 0
			count += temp // K
			if count >= M:
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


import sys

class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		if M * K == len(bloomDay):
			return max(bloomDay)
		s = min(bloomDay)
		e = max(bloomDay)
		ans = sys.maxsize
		while s <= e:
			m = (s + e) // 2
			adj = 0
			boq = 0
			for i in bloomDay:
				if i <= m:
					adj += 1
					if adj == K:
						boq += 1
						adj = 0
				else:
					adj = 0
			if boq == M:
				ans = min(ans, m)
				e = m - 1
			elif boq < M:
				s = m + 1
			else:
				e = m - 1
		return ans


class Solution:

	def solve(self, M, K, arr):
		ans = -1
		left = 1
		right = 10 ** 9
		if len(arr) < M * K:
			return -1
		while left <= right:
			mid = (left + right) // 2
			booke = 0
			count = 0
			for i in arr:
				if i <= mid:
					count += 1
					if count == K:
						booke += 1
						count = 0
				else:
					count = 0
			if booke >= M:
				right = mid - 1
				ans = mid
			else:
				left = mid + 1
		return ans


class Solution:

	def solve(self, m, k, bloomDay):
		n = len(bloomDay)
		if m * k > n:
			return -1
		low = 1
		high = max(bloomDay)
		res = -1
		while low <= high:
			mid = low + (high - low) // 2
			flower = 0
			bouq = 0
			for i in range(n):
				if bloomDay[i] > mid:
					flower = 0
				else:
					flower += 1
					if flower == k:
						bouq += 1
						flower = 0
			if bouq < m:
				low = mid + 1
			else:
				res = mid
				high = mid - 1
		return res


class Solution:

	def ifPossibletoMake(self, bloomDay, mid, m, k):
		(adj, count) = (0, 0)
		for i in range(len(bloomDay)):
			if bloomDay[i] <= mid:
				adj += 1
				if adj == k:
					count += 1
					if count == m:
						return True
					else:
						adj = 0
			else:
				adj = 0
		return False

	def solve(self, m, k, bloomDay):
		(low, high) = (min(bloomDay), max(bloomDay))
		res = -1
		if m * k > len(bloomDay):
			return -1
		while low <= high:
			mid = low + (high - low) // 2
			if self.ifPossibletoMake(bloomDay, mid, m, k):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def solve(self, M, K, bloomDay):
		flowers = M * K
		if len(bloomDay) < M * K:
			return -1
		low = 1
		high = max(bloomDay)
		ans = high
		while low <= high:
			mid = low + (high - low) // 2
			flowers = 0
			bouq = 0
			for i in range(len(bloomDay)):
				if bloomDay[i] > mid:
					flowers = 0
				else:
					flowers += 1
					if flowers >= K:
						bouq += 1
						flowers = 0
			if bouq < M:
				low = mid + 1
			else:
				ans = min(ans, mid)
				high = mid - 1
		return ans


import math

class Solution:

	def canMakeBouquets(self, bouquets, adjFlowers, bloomDay, mid):
		noBouquets = 0
		currFlowers = 0
		for day in bloomDay:
			if day <= mid:
				currFlowers += 1
			else:
				currFlowers = 0
			if currFlowers == adjFlowers:
				noBouquets += 1
				currFlowers = 0
		return noBouquets >= bouquets

	def solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		low = min(bloomDay)
		high = max(bloomDay)
		min_days = math.inf
		while low <= high:
			mid = low + high >> 1
			if self.canMakeBouquets(M, K, bloomDay, mid):
				min_days = min(min_days, mid)
				high = mid - 1
			else:
				low = mid + 1
		if min_days == math.inf:
			return -1
		return min_days


class Solution:

	def solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		(l, r) = (1, max(bloomDay))
		res = -1
		while l <= r:
			cnt = 0
			sums = 0
			mid = (l + r) // 2
			for i in bloomDay:
				if mid / i >= 1:
					sums += 1
					if sums == K:
						cnt += 1
						sums = 0
				else:
					sums = 0
			if cnt >= M:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, M, K, arr):
		k = K
		m = M
		if len(arr) < k * m:
			return -1
		(l, r) = (1, max(arr))
		res = -1
		while l <= r:
			count = 0
			sum = 0
			mid = (l + r) // 2
			for i in arr:
				if mid / i >= 1:
					sum += 1
					if sum == k:
						count += 1
						sum = 0
				else:
					sum = 0
			if count >= m:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, M, K, bloomDay):

		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
		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 solve(self, M, K, bloomDay):
		if len(bloomDay) < M * K:
			return -1
		left = 0
		right = max(bloomDay)
		while left < right:
			flw = bq = 0
			mid = left + right >> 1
			for a in bloomDay:
				if a > mid:
					flw = 0
				else:
					flw += 1
				if flw >= K:
					flw = 0
					bq += 1
					if bq == M:
						break
			if bq == M:
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		n = len(bloomDay)
		low = min(bloomDay)
		high = max(bloomDay)
		while low <= high:
			mid = low + high >> 1
			(total, ans) = (0, 0)
			for i in range(n):
				if mid >= bloomDay[i]:
					ans += 1
				else:
					ans = 0
				if ans == K:
					total += 1
					ans = 0
			if total >= M:
				high = mid - 1
			else:
				low = mid + 1
		return low


class Solution:

	def check(self, x):
		count = bouquets = 0
		for d in bloomDay:
			if d <= x:
				count += 1
				if count == K:
					bouquets += 1
					count = 0
			else:
				count = 0
		return bouquets >= M

	def solve(self, M, K, bloomDay):
		n = len(bloomDay)
		if M * K > len(bloomDay):
			return -1
		(l, r) = (0, max(bloomDay) + 1)
		while l < r:
			m = (l + r) // 2
			if self.check(m):
				r = m - 1
			else:
				l = m + 1
		if self.check(l):
			return l
		else:
			return l + 1


import math

class Solution:

	def solve(self, M, K, bloomDay):

		def possible(mid, M, K):
			count = 0
			bouq = 0
			for i in bloomDay:
				if i <= mid:
					count += 1
					if count == K:
						bouq += 1
						count = 0
				else:
					count = 0
			if bouq >= M:
				return True
			return False
		if M * K > len(bloomDay):
			return -1
		s = 1
		e = max(bloomDay)
		while s <= e:
			mid = (s + e) // 2
			if possible(mid, M, K):
				e = mid - 1
			else:
				s = mid + 1
		return s


class Solution:

	def canWork(self, blooms, days, m, k):
		flowers = 0
		for flower in blooms:
			flowers = flowers + 1 if flower <= days else 0
			if flowers == k:
				m -= 1
				flowers = 0
		return m <= 0

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


class Solution:

	def check(self, arr, m, k, mid):
		total = 0
		con = 0
		for i in arr:
			if i <= mid:
				con += 1
			else:
				con = 0
			if con == k:
				total += 1
				con = 0
		if total >= m:
			return True
		return False

	def solve(self, m, k, bloomDay):
		if m * k > len(bloomDay):
			return -1
		start = min(bloomDay)
		end = max(bloomDay)
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			if self.check(bloomDay, m, k, mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def getTotal(self, bloomday, mid, K):
		(result, count) = (0, 0)
		for i in range(len(bloomday)):
			if bloomday[i] <= mid:
				count += 1
			else:
				count = 0
			if count == K:
				result += 1
				count = 0
		return result

	def solve(self, M, K, bloomDay):
		if M * K > len(bloomDay):
			return -1
		(low, high) = (1, max(bloomDay))
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			total = self.getTotal(bloomDay, mid, K)
			if total >= M:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def solve(self, m, k, bloomDay):
		n = len(bloomDay)
		if m * k > n:
			return -1
		(l, r) = (min(bloomDay), max(bloomDay))
		while l < r:
			mid = l + (r - l) // 2
			if self.form_bouquet(bloomDay, mid, m, k):
				r = mid
			else:
				l = mid + 1
		return l

	def form_bouquet(self, bloomDay, day, m, k):
		idx_greater_day = []
		for i in range(len(bloomDay)):
			if bloomDay[i] <= day:
				idx_greater_day.append(i)
		bouquet_count = 0
		i = 0
		while i < len(idx_greater_day):
			j = i + 1
			while j < len(idx_greater_day) and j - i < k and (idx_greater_day[j] == idx_greater_day[j - 1] + 1):
				j += 1
			if j - i == k:
				bouquet_count += 1
			i = j
		return bouquet_count >= m


class Solution:

	def solve(self, M, K, bloomDay):
		N = len(bloomDay)
		if M * K > N:
			return -1
		low = 1
		high = 1000000000
		while low <= high:
			mid = int((low + high) // 2)
			boquentMade = self.makeBoquet(bloomDay, N, K, mid)
			if boquentMade >= M:
				high = mid - 1
			else:
				low = mid + 1
		return low

	def makeBoquet(self, bloomDay, N, K, mid):
		NoOfBoquet = 0
		start = N
		while N - 1 >= 0:
			if bloomDay[N - 1] <= mid:
				if start - (N - 1) == K:
					NoOfBoquet += 1
					start = N - 1
			else:
				start = N - 1
			N -= 1
		return NoOfBoquet