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



def  __lowerCamelCase       (      _UpperCamelCase  :  list[int]					):  # This function is recursive


      '''simple docstring'''


      UpperCAmelCase_            =  len(_UpperCamelCase					)
      # If the array contains only one element, we return it (it's the stop condition of
      # recursion)
      if array_length <= 1:
            return array
            # Else
      UpperCAmelCase_            =  array[0]
      UpperCAmelCase_            =  False
      UpperCAmelCase_            =  1
      UpperCAmelCase_            =  []
      while not is_found and i < array_length:
            if array[i] < pivot:
                  UpperCAmelCase_            =  True
                  UpperCAmelCase_            =  [element for element in array[i:] if element >= array[i]]
                  UpperCAmelCase_            =  longest_subsequence(_UpperCamelCase					)
                  if len(_UpperCamelCase					) > len(_UpperCamelCase					):
                        UpperCAmelCase_            =  temp_array
            else:
                  i += 1

      UpperCAmelCase_            =  [element for element in array[1:] if element >= pivot]
      UpperCAmelCase_            =  [pivot, *longest_subsequence(_UpperCamelCase					)]
      if len(_UpperCamelCase					) > len(_UpperCamelCase					):
            return temp_array
      else:
            return longest_subseq


if __name__ == "__main__":
       import doctest

       doctest.testmod()






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



def  __lowerCamelCase       (      _UpperCamelCase  :  tuple[int, int]							,    _UpperCamelCase  :  int					):


      '''simple docstring'''


      UpperCAmelCase_      ,		UpperCAmelCase_            =  position
      UpperCAmelCase_            =  [
          (y + 1, x + 2),
          (y - 1, x + 2),
          (y + 1, x - 2),
          (y - 1, x - 2),
          (y + 2, x + 1),
          (y + 2, x - 1),
          (y - 2, x + 1),
          (y - 2, x - 1),
      ]
      UpperCAmelCase_            =  []

      for position in positions:
            UpperCAmelCase_      ,		UpperCAmelCase_            =  position
            if 0 <= y_test < n and 0 <= x_test < n:
                  permissible_positions.append(_UpperCamelCase					)

      return permissible_positions



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]					):


      '''simple docstring'''


      return not any(elem == 0 for row in board for elem in row					)



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]							,    _UpperCamelCase  :  tuple[int, int]							,    _UpperCamelCase  :  int					):


      '''simple docstring'''


      if is_complete(_UpperCamelCase					):
            return True

      for position in get_valid_pos(_UpperCamelCase							,    len(_UpperCamelCase					)					):
            UpperCAmelCase_      ,		UpperCAmelCase_            =  position

            if board[y][x] == 0:
                  UpperCAmelCase_            =  curr + 1
                  if open_knight_tour_helper(_UpperCamelCase							,    _UpperCamelCase							,    curr + 1					):
                        return True
                  UpperCAmelCase_            =  0

      return False



def  __lowerCamelCase       (      _UpperCamelCase  :  int					):


      '''simple docstring'''


      UpperCAmelCase_            =  [[0 for i in range(_UpperCamelCase					)] for j in range(_UpperCamelCase					)]

      for i in range(_UpperCamelCase					):
            for j in range(_UpperCamelCase					):
                  UpperCAmelCase_            =  1
                  if open_knight_tour_helper(_UpperCamelCase							,    (i, j)							,    1					):
                        return board
                  UpperCAmelCase_            =  0

      UpperCAmelCase_            =  F"""Open Kight Tour cannot be performed on a board of size {n}"""
      raise ValueError(_UpperCamelCase					)


if __name__ == "__main__":
      import doctest

      doctest.testmod()





