



'''simple docstring'''

from collections.abc import Sequence
from queue import Queue

class __snake_case:


						'''simple docstring'''



						def __init__(   self      ,			A_      ,			A_      ,			A_      ,			A_=None      ,			A_=None )      ->      Optional[int]:
							lowerCAmelCase       =      start
							lowerCAmelCase       =      end
							lowerCAmelCase       =      val
							lowerCAmelCase       =      (start + end) // 2
							lowerCAmelCase       =      left
							lowerCAmelCase       =      right




						def __repr__(   self )      ->      Any:
							return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'







class __snake_case:


						'''simple docstring'''



						def __init__(   self      ,			A_      ,			A_ )      ->      int:
							lowerCAmelCase       =      collection
							lowerCAmelCase       =      function
							if self.collection:
								lowerCAmelCase       =      self._build_tree(0      ,			len(UpperCamelCase__ ) - 1 )


						def 							__snake_case       (   self      ,			A_      ,			A_ )      ->      Any:
							self._update_tree(self.root      ,			UpperCamelCase__      ,			UpperCamelCase__ )


						def 							__snake_case       (   self      ,			A_      ,			A_ )      ->      List[str]:
							return self._query_range(self.root      ,			UpperCamelCase__      ,			UpperCamelCase__ )


						def 							__snake_case       (   self      ,			A_      ,			A_ )      ->      int:






							if start == end:
								return SegmentTreeNode(UpperCamelCase__      ,			UpperCamelCase__      ,			self.collection[start] )
							lowerCAmelCase       =      (start + end) // 2
							lowerCAmelCase       =      self._build_tree(UpperCamelCase__      ,			UpperCamelCase__ )
							lowerCAmelCase       =      self._build_tree(mid + 1      ,			UpperCamelCase__ )
							return SegmentTreeNode(UpperCamelCase__      ,			UpperCamelCase__      ,			self.fn(left.val      ,			right.val )      ,			UpperCamelCase__      ,			UpperCamelCase__ )


						def 							__snake_case       (   self      ,			A_      ,			A_      ,			A_ )      ->      str:






							if node.start == i and node.end == i:
								lowerCAmelCase       =      val
								return
							if i <= node.mid:
								self._update_tree(node.left      ,			UpperCamelCase__      ,			UpperCamelCase__ )
							else:
								self._update_tree(node.right      ,			UpperCamelCase__      ,			UpperCamelCase__ )
							lowerCAmelCase       =      self.fn(node.left.val      ,			node.right.val )


						def 							__snake_case       (   self      ,			A_      ,			A_      ,			A_ )      ->      Any:






							if node.start == i and node.end == j:
								return node.val

							if i <= node.mid:
								if j <= node.mid:
									# range in left child tree
									return self._query_range(node.left      ,			UpperCamelCase__      ,			UpperCamelCase__ )
								else:
									# range in left child tree and right child tree
									return self.fn(
									    self._query_range(node.left      ,			UpperCamelCase__      ,			node.mid )      ,			self._query_range(node.right      ,			node.mid + 1      ,			UpperCamelCase__ )      ,			)
							else:
								# range in right child tree
								return self._query_range(node.right      ,			UpperCamelCase__      ,			UpperCamelCase__ )




						def 							__snake_case       (   self )      ->      List[Any]:






							if self.root is not None:
								lowerCAmelCase       =      Queue()
								queue.put(self.root )
								while not queue.empty():
									lowerCAmelCase       =      queue.get()
									yield node

									if node.left is not None:
										queue.put(node.left )

									if node.right is not None:
										queue.put(node.right )


if __name__ == "__main__":
				import operator

				for fn in [operator.add, max, min]:
								print('*' * 50)
								UpperCAmelCase      						=       SegmentTree([2, 1, 5, 3, 4], fn)
								for node in arr.traverse():
												print(node)
								print()

								arr.update(1, 5)
								for node in arr.traverse():
												print(node)
								print()

								print(arr.query_range(3, 4))  # 7
								print(arr.query_range(2, 2))  # 5
								print(arr.query_range(1, 3))  # 13
								print()

from __future__ import annotations

def a__       (			A_,	A_,	A_,	A_   ):






  '''simple docstring'''





  if (direction == 1 and array[indexa] > array[indexa]) or (
      direction == 0 and array[indexa] < array[indexa]
  ):
    __magic_name__	,       __magic_name__								=			array[indexa], array[indexa]

def a__       (			A_,	A_,	A_,	A_   ):






  '''simple docstring'''





  if length > 1:
    __magic_name__								=			int(length / 2   )
    for i in range(A_,	low + middle   ):
      comp_and_swap(A_,	A_,	i + middle,	A_   )
    bitonic_merge(A_,	A_,	A_,	A_   )
    bitonic_merge(A_,	low + middle,	A_,	A_   )

def a__       (			A_,	A_,	A_,	A_   ):






  '''simple docstring'''





  if length > 1:
    __magic_name__								=			int(length / 2   )
    bitonic_sort(A_,	A_,	A_,	1   )
    bitonic_sort(A_,	low + middle,	A_,	0   )
    bitonic_merge(A_,	A_,	A_,	A_   )


if __name__ == "__main__":
    __lowerCAmelCase     :	Optional[Any]       			=  input('Enter numbers separated by a comma:\n').strip()
    __lowerCAmelCase     :	List[Any]       			=  [int(item.strip()) for item in user_input.split(',')]

    bitonic_sort(unsorted, 0, len(unsorted), 1)
    print('\nSorted array in ascending order is: ', end='')
    print(*unsorted, sep=', ')

    bitonic_merge(unsorted, 0, len(unsorted), 0)
    print('Sorted array in descending order is: ', end='')
    print(*unsorted, sep=', ')

