






'''simple docstring'''
from __future__ import annotations

import math



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   if len(_UpperCamelCase							) != 2 or len(a[0]							) != 2 or len(_UpperCamelCase							) != 2 or len(b[0]							) != 2:
      raise Exception("Matrices are not 2x2"							)
   lowercase_	:    Any           =     [
       [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
       [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
   ]
   return new_matrix



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   return [
       [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]							)							)]
       for row in range(len(_UpperCamelCase							)							)
   ]



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   return [
       [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]							)							)]
       for row in range(len(_UpperCamelCase							)							)
   ]



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   if len(_UpperCamelCase							) % 2 != 0 or len(a[0]							) % 2 != 0:
      raise Exception("Odd matrices are not supported!"							)

   lowercase_	:    List[Any]           =     len(_UpperCamelCase							)
   lowercase_	:    Dict           =     matrix_length // 2

   lowercase_	:    str           =     [[a[i][j] for j in range(_UpperCamelCase						,		_UpperCamelCase							)] for i in range(_UpperCamelCase							)]
   lowercase_	:    int           =     [
       [a[i][j] for j in range(_UpperCamelCase						,		_UpperCamelCase							)] for i in range(_UpperCamelCase						,		_UpperCamelCase							)
   ]

   lowercase_	:    Tuple           =     [[a[i][j] for j in range(_UpperCamelCase							)] for i in range(_UpperCamelCase							)]
   lowercase_	:    Union[str, Any]           =     [[a[i][j] for j in range(_UpperCamelCase							)] for i in range(_UpperCamelCase						,		_UpperCamelCase							)]

   return top_left, top_right, bot_left, bot_right



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   return len(_UpperCamelCase							), len(matrix[0]							)



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   print("\n".join(str(_UpperCamelCase							) for line in matrix							)							)



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   if matrix_dimensions(_UpperCamelCase							) == (2, 2):
      return default_matrix_multiplication(_UpperCamelCase						,		_UpperCamelCase							)

   lowercase_	:    List[str]           =     split_matrix(_UpperCamelCase							)
   lowercase_	:    Any           =     split_matrix(_UpperCamelCase							)

   lowercase_	:    Optional[int]           =     actual_strassen(_UpperCamelCase						,		matrix_subtraction(_UpperCamelCase						,		_UpperCamelCase							)							)
   lowercase_	:    List[Any]           =     actual_strassen(matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)						,		_UpperCamelCase							)
   lowercase_	:    Any           =     actual_strassen(matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)						,		_UpperCamelCase							)
   lowercase_	:    List[Any]           =     actual_strassen(_UpperCamelCase						,		matrix_subtraction(_UpperCamelCase						,		_UpperCamelCase							)							)
   lowercase_	:    List[str]           =     actual_strassen(matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)						,		matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)							)
   lowercase_	:    Optional[int]           =     actual_strassen(matrix_subtraction(_UpperCamelCase						,		_UpperCamelCase							)						,		matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)							)
   lowercase_	:    List[str]           =     actual_strassen(matrix_subtraction(_UpperCamelCase						,		_UpperCamelCase							)						,		matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)							)

   lowercase_	:    Dict           =     matrix_addition(matrix_subtraction(matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)						,		_UpperCamelCase							)						,		_UpperCamelCase							)
   lowercase_	:    List[Any]           =     matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)
   lowercase_	:    List[str]           =     matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)
   lowercase_	:    Dict           =     matrix_subtraction(matrix_subtraction(matrix_addition(_UpperCamelCase						,		_UpperCamelCase							)						,		_UpperCamelCase							)						,		_UpperCamelCase							)

   # construct the new matrix from our 4 quadrants
   lowercase_	:    Union[str, Any]           =     []
   for i in range(len(_UpperCamelCase							)							):
      new_matrix.append(top_left[i] + top_right[i]							)
   for i in range(len(_UpperCamelCase							)							):
      new_matrix.append(bot_left[i] + bot_right[i]							)
   return new_matrix



def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   if matrix_dimensions(_UpperCamelCase							)[1] != matrix_dimensions(_UpperCamelCase							)[0]:
      lowercase_	:    Union[str, Any]           =     (
          "Unable to multiply these matrices, please check the dimensions.\n"
          F"""Matrix A: {matrixa}\n"""
          F"""Matrix B: {matrixa}"""
      )
      raise Exception(_UpperCamelCase							)
   lowercase_	:    List[Any]           =     matrix_dimensions(_UpperCamelCase							)
   lowercase_	:    str           =     matrix_dimensions(_UpperCamelCase							)

   if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
      return [matrixa, matrixa]

   lowercase_	:    Any           =     max(*_UpperCamelCase						,		*_UpperCamelCase							)
   lowercase_	:    str           =     int(math.pow(2						,		math.ceil(math.loga(_UpperCamelCase							)							)							)							)
   lowercase_	:    Union[str, Any]           =     matrixa
   lowercase_	:    List[str]           =     matrixa

   # Adding zeros to the matrices so that the arrays dimensions are the same and also
   # power of 2
   for i in range(0						,		_UpperCamelCase							):
      if i < dimensiona[0]:
         for _ in range(dimensiona[1]						,		_UpperCamelCase							):
            new_matrixa[i].append(0							)
      else:
         new_matrixa.append([0] * maxim							)
      if i < dimensiona[0]:
         for _ in range(dimensiona[1]						,		_UpperCamelCase							):
            new_matrixa[i].append(0							)
      else:
         new_matrixa.append([0] * maxim							)

   lowercase_	:    Optional[Any]           =     actual_strassen(_UpperCamelCase						,		_UpperCamelCase							)

   # Removing the additional zeros
   for i in range(0						,		_UpperCamelCase							):
      if i < dimensiona[0]:
         for _ in range(dimensiona[1]						,		_UpperCamelCase							):
            final_matrix[i].pop()
      else:
         final_matrix.pop()
   return final_matrix


if __name__ == "__main__":
 UpperCamelCase__ =			[
     [2, 3, 4, 5],
     [6, 4, 3, 1],
     [2, 3, 6, 7],
     [3, 1, 2, 4],
     [2, 3, 4, 5],
     [6, 4, 3, 1],
     [2, 3, 6, 7],
     [3, 1, 2, 4],
     [2, 3, 4, 5],
     [6, 2, 3, 1],
 ]
 UpperCamelCase__ =			[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
 print(strassen(matrixa, matrixa))












'''simple docstring'''
from __future__ import annotations

UpperCamelCase__ =			[-10, -5, 0, 5, 5.1, 11, 13, 21, 3, 4, -21, -10, -5, -1, 0]
UpperCamelCase__ =			[-5, 0, 5, 5.1, 11, 13, 21, -1, 4, -1, -10, -5, -1, 0, -1]




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    str           =     []
   lowercase_	:    List[str]           =     len(_UpperCamelCase							)

   for i in range(_UpperCamelCase							):
      lowercase_	:    float           =     -1
      for j in range(i + 1						,		_UpperCamelCase							):
         if arr[i] < arr[j]:
            lowercase_	:    Union[str, Any]           =     arr[j]
            break
      result.append(_UpperCamelCase							)
   return result




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    List[str]           =     []
   for i, outer in enumerate(_UpperCamelCase							):
      lowercase_	:    float           =     -1
      for inner in arr[i + 1 :]:
         if outer < inner:
            lowercase_	:    Optional[Any]           =     inner
            break
      result.append(_UpperCamelCase							)
   return result




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    List[str]           =     len(_UpperCamelCase							)
   lowercase_	:    list[float]           =     []
   lowercase_	:    list[float]           =     [-1] * arr_size

   for index in reversed(range(_UpperCamelCase							)							):
      if stack:
         while stack[-1] <= arr[index]:
            stack.pop()
            if not stack:
               break
      if stack:
         lowercase_	:    Optional[Any]           =     stack[-1]
      stack.append(arr[index]							)
   return result


if __name__ == "__main__":
 from doctest import testmod
 from timeit import timeit

 testmod()
 print(next_greatest_element_slow(arr))
 print(next_greatest_element_fast(arr))
 print(next_greatest_element(arr))

 UpperCamelCase__ =			(
     'from __main__ import arr, next_greatest_element_slow, '
     'next_greatest_element_fast, next_greatest_element'
 )
 print(
     'next_greatest_element_slow():',
     timeit('next_greatest_element_slow(arr)', setup=setup),
 )
 print(
     'next_greatest_element_fast():',
     timeit('next_greatest_element_fast(arr)', setup=setup),
 )
 print(
     '     next_greatest_element():',
     timeit('next_greatest_element(arr)', setup=setup),
 )




