

from math import ceil

def  lowerCamelCase__ (					_a							,			_a):
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       list(range(0							,			_a))

	SCREAMING_SNAKE_CASE   :      Tuple				     =       [item for sublist in list(device_map.values()) for item in sublist]

	# Duplicate check
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       []
	for i in device_map_blocks:
		if device_map_blocks.count(_a) > 1 and i not in duplicate_blocks:
			duplicate_blocks.append(_a)
    # Missing blocks
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       [i for i in blocks if i not in device_map_blocks]
	SCREAMING_SNAKE_CASE   :      Any				     =       [i for i in device_map_blocks if i not in blocks]

	if len(_a) != 0:
		raise ValueError(
		    "Duplicate attention blocks specified in device_map. Attention blocks must be specified to one device."
		    " These attention blocks were specified more than once: " + str(_a))
	if len(_a) != 0:
		raise ValueError(
		    "There are attention blocks for this model that are not specified in the device_map. Add these attention "
		    "blocks to a device on the device_map: " + str(_a))
	if len(_a) != 0:
		raise ValueError(
		    "The device_map contains more attention blocks than this model has. Remove these from the device_map:"
		    + str(_a))


def  lowerCamelCase__ (					_a							,			_a):
	SCREAMING_SNAKE_CASE   :      Dict				     =       list(range(_a))
	SCREAMING_SNAKE_CASE   :      Any				     =       int(ceil(n_layers / len(_a)))
	SCREAMING_SNAKE_CASE   :      Dict				     =       [layers[i : i + n_blocks] for i in range(0							,			_a							,			_a)]

	return dict(zip(_a							,			_a))


class _UpperCamelCase							:
			'''simple docstring'''







			def __init__(			self							: Optional[Any]      ,      a							: int	)							->       None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE   :      Tuple				     =       size
				SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       [0] * size
				SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       [0] * size
			@staticmethod
			def 							__UpperCamelCase (			a							: int	)							->       int:

				"""simple docstring"""

				return index | (index + 1)
			@staticmethod
			def 							__UpperCamelCase (			a							: int	)							->       int:

				"""simple docstring"""

				return (index & (index + 1)) - 1
			def 							__UpperCamelCase (			self							: Any      ,      a							: int      ,      a							: int	)							->       None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       value
				while index < self.size:
					SCREAMING_SNAKE_CASE   :      Dict				     =       self.get_prev(a	) + 1
					if current_left_border == index:
						SCREAMING_SNAKE_CASE   :      Optional[int]				     =       value
					else:
						SCREAMING_SNAKE_CASE   :      Tuple				     =       max(a      ,      a      ,      a	)
					SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       self.get_next(a	)






			def 							__UpperCamelCase (			self							: Optional[int]      ,      a							: int      ,      a							: int	)							->       int:

				"""simple docstring"""

				right -= 1  # Because of right is exclusive
				SCREAMING_SNAKE_CASE   :      Optional[int]				     =       0
				while left <= right:
					SCREAMING_SNAKE_CASE   :      List[Any]				     =       self.get_prev(a	)
					if left <= current_left:
						SCREAMING_SNAKE_CASE   :      List[Any]				     =       max(a      ,      self.tree[right]	)
						SCREAMING_SNAKE_CASE   :      str				     =       current_left
					else:
						SCREAMING_SNAKE_CASE   :      List[str]				     =       max(a      ,      self.arr[right]	)
						right -= 1
				return result


if __name__ == "__main__":
			import doctest

			doctest.testmod()