




import os
import string
import sys


lowerCamelCase__					:  Any      							=				1 << 8

lowerCamelCase__					:  Optional[int]      							=				{
    'tab': ord('\t'),
    'newline': ord('\r'),
    'esc': 27,
    'up': 65 + ARROW_KEY_FLAG,
    'down': 66 + ARROW_KEY_FLAG,
    'right': 67 + ARROW_KEY_FLAG,
    'left': 68 + ARROW_KEY_FLAG,
    'mod_int': 91,
    'undefined': sys.maxsize,
    'interrupt': 3,
    'insert': 50,
    'delete': 51,
    'pg_up': 53,
    'pg_down': 54,
}

lowerCamelCase__					:  Dict      							=				KEYMAP['up']
lowerCamelCase__					:  int      							=				KEYMAP['left']

if sys.platform == "win32":
   lowerCamelCase__					:  Any      							=				[]
   lowerCamelCase__					:  List[str]      							=				{
       b'\xe0H': KEYMAP['up'] - ARROW_KEY_FLAG,
       b'\x00H': KEYMAP['up'] - ARROW_KEY_FLAG,
       b'\xe0P': KEYMAP['down'] - ARROW_KEY_FLAG,
       b'\x00P': KEYMAP['down'] - ARROW_KEY_FLAG,
       b'\xe0M': KEYMAP['right'] - ARROW_KEY_FLAG,
       b'\x00M': KEYMAP['right'] - ARROW_KEY_FLAG,
       b'\xe0K': KEYMAP['left'] - ARROW_KEY_FLAG,
       b'\x00K': KEYMAP['left'] - ARROW_KEY_FLAG,
   }

for i in range(10):
   lowerCamelCase__					:  Union[str, Any]      							=				ord(str(i))

def    UpperCAmelCase_				( )   ->					Dict:
      if os.name == "nt":
            import msvcrt

            SCREAMING_SNAKE_CASE_      		=     'mbcs'
            # Flush the keyboard buffer
            while msvcrt.kbhit():
                  msvcrt.getch()
            if len(__UpperCAmelCase				) == 0:
                  # Read the keystroke
                  SCREAMING_SNAKE_CASE_      		=     msvcrt.getch()

                  # If it is a prefix char, get second part
                  if ch in (b"\x00", b"\xe0"):
                        SCREAMING_SNAKE_CASE_      		=     ch + msvcrt.getch()
                        # Translate actual Win chars to bullet char types
                        try:
                              SCREAMING_SNAKE_CASE_      		=     chr(WIN_KEYMAP[cha]				)
                              WIN_CH_BUFFER.append(chr(KEYMAP['mod_int']				)				)
                              WIN_CH_BUFFER.append(__UpperCAmelCase				)
                              if ord(__UpperCAmelCase				) in (
                                  KEYMAP["insert"] - 1 << 9,
                                  KEYMAP["delete"] - 1 << 9,
                                  KEYMAP["pg_up"] - 1 << 9,
                                  KEYMAP["pg_down"] - 1 << 9,
                              ):
                                    WIN_CH_BUFFER.append(chr(1_26				)				)
                              SCREAMING_SNAKE_CASE_      		=     chr(KEYMAP['esc']				)
                        except KeyError:
                              SCREAMING_SNAKE_CASE_      		=     cha[1]
                  else:
                        SCREAMING_SNAKE_CASE_      		=     ch.decode(__UpperCAmelCase				)
            else:
                  SCREAMING_SNAKE_CASE_      		=     WIN_CH_BUFFER.pop(0				)
      elif os.name == "posix":
            import termios
            import tty

            SCREAMING_SNAKE_CASE_      		=     sys.stdin.fileno()
            SCREAMING_SNAKE_CASE_      		=     termios.tcgetattr(__UpperCAmelCase				)
            try:
                  tty.setraw(__UpperCAmelCase				)
                  SCREAMING_SNAKE_CASE_      		=     sys.stdin.read(1				)
            finally:
                  termios.tcsetattr(__UpperCAmelCase     ,     termios.TCSADRAIN     ,     __UpperCAmelCase				)
      return ch





def    UpperCAmelCase_				( )   ->					List[str]:
      SCREAMING_SNAKE_CASE_      		=     get_raw_chars()
      if ord(__UpperCAmelCase				) in [KEYMAP["interrupt"], KEYMAP["newline"]]:
            return char

      elif ord(__UpperCAmelCase				) == KEYMAP["esc"]:
            SCREAMING_SNAKE_CASE_      		=     get_raw_chars()
            if ord(__UpperCAmelCase				) == KEYMAP["mod_int"]:
                  SCREAMING_SNAKE_CASE_      		=     get_raw_chars()
                  if ord(__UpperCAmelCase				) >= KEYMAP["arrow_begin"] - ARROW_KEY_FLAG and ord(__UpperCAmelCase				) <= KEYMAP["arrow_end"] - ARROW_KEY_FLAG:
                        return chr(ord(__UpperCAmelCase				) + ARROW_KEY_FLAG				)
                  else:
                        return KEYMAP["undefined"]
            else:
                  return get_raw_chars()

      else:
            if char in string.printable:
                  return char
            else:
                  return KEYMAP["undefined"]





"""simple docstring"""






from __future__ import annotations







def 	_snake_case     (							lowercase__						):  # This function is recursive
				_lowerCamelCase	:     Optional[Any]       =       len(lowercase__						)
				# If the array contains only one element, we return it (it's the stop condition of
				# recursion)
				if array_length <= 1:
								return array
								# Else
				_lowerCamelCase	:     Optional[Any]       =       array[0]
				_lowerCamelCase	:     Optional[int]       =       False
				_lowerCamelCase	:     List[str]       =       1
				_lowerCamelCase	:     list[int]       =       []
				while not is_found and i < array_length:
								if array[i] < pivot:
												_lowerCamelCase	:     Union[str, Any]       =       True
												_lowerCamelCase	:     str       =       [element for element in array[i:] if element >= array[i]]
												_lowerCamelCase	:     str       =       longest_subsequence(lowercase__						)
												if len(lowercase__						) > len(lowercase__						):
																_lowerCamelCase	:     Any       =       temp_array
								else:
												i += 1

				_lowerCamelCase	:     Optional[Any]       =       [element for element in array[1:] if element >= pivot]
				_lowerCamelCase	:     Dict       =       [pivot, *longest_subsequence(lowercase__						)]
				if len(lowercase__						) > len(lowercase__						):
								return temp_array
				else:
								return longest_subseq


if __name__ == "__main__":
			import doctest

			doctest.testmod()