






'''simple docstring'''







import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin


if is_torch_available():
			import torch

if is_vision_available():
			from PIL import Image

			from transformers import TvltImageProcessor





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase=10							,     UpperCamelCase=10							,     UpperCamelCase=False							,     UpperCamelCase=False ) ->			Optional[int]:
							lowerCamelCase__   :      Dict			    =			[]
							for i in range(image_processor_tester.num_frames ):
														video.append(np.random.randint(255							,     size=(image_processor_tester.num_channels, width, height)							,     dtype=np.uinta ) )

							if not numpify and not torchify:
														# PIL expects the channel dimension as last dimension
														lowerCamelCase__   :      int			    =			[Image.fromarray(np.moveaxis(UpperCamelCase							,     0							,     -1 ) ) for frame in video]

							if torchify:
														lowerCamelCase__   :      Tuple			    =			[torch.from_numpy(UpperCamelCase ) for frame in video]

							return video





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase=False							,     UpperCamelCase=False							,     UpperCamelCase=False ) ->			List[str]:
							assert not (numpify and torchify), "You cannot specify both numpy and PyTorch tensors at the same time"

							lowerCamelCase__   :      Any			    =			[]
							for i in range(image_processor_tester.batch_size ):
														if equal_resolution:
																					lowerCamelCase__   :      Tuple			    =			image_processor_tester.max_resolution
														else:
																					lowerCamelCase__    ,						lowerCamelCase__   :      str			    =			np.random.choice(
																					    np.arange(image_processor_tester.min_resolution							,     image_processor_tester.max_resolution )							,     2 )
																					lowerCamelCase__   :      Union[str, Any]			    =			prepare_video(
																					    image_processor_tester=UpperCamelCase							,     width=UpperCamelCase							,     height=UpperCamelCase							,     numpify=UpperCamelCase							,     torchify=UpperCamelCase							,     )
														video_inputs.append(UpperCamelCase )

							return video_inputs

class _lowercase      (							unittest.TestCase						):




							def __init__(				self:							Optional[int]     ,				UpperCamelCase__:							Optional[int]     ,				UpperCamelCase__:							List[Any]=7     ,				UpperCamelCase__:							Any=3     ,				UpperCamelCase__:							str=4     ,				UpperCamelCase__:							List[Any]=18     ,				UpperCamelCase__:							List[str]=30     ,				UpperCamelCase__:							Optional[int]=400     ,				UpperCamelCase__:							Optional[Any]=True     ,				UpperCamelCase__:							Optional[Any]=None     ,				UpperCamelCase__:							Any=True     ,				UpperCamelCase__:							str=[0.5, 0.5, 0.5]     ,				UpperCamelCase__:							str=[0.5, 0.5, 0.5]     ,				UpperCamelCase__:							Any=True     ,				UpperCamelCase__:							Union[str, Any]=None     ,				):
														lowerCamelCase__   :      Optional[Any]			    =			size if size is not None else {"""shortest_edge""": 18}
														lowerCamelCase__   :      List[Any]			    =			crop_size if crop_size is not None else {"""height""": 18, """width""": 18}

														lowerCamelCase__   :      str			    =			parent
														lowerCamelCase__   :      Dict			    =			batch_size
														lowerCamelCase__   :      Optional[int]			    =			num_channels
														lowerCamelCase__   :      List[Any]			    =			num_frames
														lowerCamelCase__   :      int			    =			image_size
														lowerCamelCase__   :      List[Any]			    =			min_resolution
														lowerCamelCase__   :      Union[str, Any]			    =			max_resolution
														lowerCamelCase__   :      Optional[int]			    =			do_resize
														lowerCamelCase__   :      Optional[int]			    =			size
														lowerCamelCase__   :      Union[str, Any]			    =			do_normalize
														lowerCamelCase__   :      int			    =			image_mean
														lowerCamelCase__   :      Dict			    =			image_std
														lowerCamelCase__   :      List[str]			    =			do_center_crop
														lowerCamelCase__   :      Optional[Any]			    =			crop_size




							def 						lowerCamelCase_							(				self:							List[str]	):
														return {
														    "image_mean": self.image_mean,
														    "image_std": self.image_std,
														    "do_normalize": self.do_normalize,
														    "do_resize": self.do_resize,
														    "size": self.size,
														    "do_center_crop": self.do_center_crop,
														    "crop_size": self.crop_size,
														}



@require_torch
@require_vision
class _lowercase      (							_lowercase							, unittest.TestCase						):
							a							 =			TvltImageProcessor if is_vision_available() else None




							def 						lowerCamelCase_							(				self:							Dict	):
														lowerCamelCase__   :      Optional[int]			    =			TvltImageProcessorTester(self	)




							@property
							def 						lowerCamelCase_							(				self:							List[Any]	):
														return self.image_processor_tester.prepare_image_processor_dict()




							def 						lowerCamelCase_							(				self:							Optional[Any]	):
														lowerCamelCase__   :      Union[str, Any]			    =			self.image_processing_class(**self.image_processor_dict	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""image_mean"""	)	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""image_std"""	)	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""do_normalize"""	)	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""do_resize"""	)	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""do_center_crop"""	)	)
														self.assertTrue(hasattr(UpperCamelCase__     ,				"""size"""	)	)




							def 						lowerCamelCase_							(				self:							Optional[Any]	):
														# Initialize image_processor
														lowerCamelCase__   :      List[str]			    =			self.image_processing_class(**self.image_processor_dict	)
														# create random PIL videos
														lowerCamelCase__   :      List[str]			    =			prepare_video_inputs(self.image_processor_tester     ,				equal_resolution=UpperCamelCase__	)
														for video in video_inputs:
																					self.assertIsInstance(UpperCamelCase__     ,				UpperCamelCase__	)
																					self.assertIsInstance(video[0]     ,				Image.Image	)

														# Test not batched input
														lowerCamelCase__   :      List[str]			    =			image_processor(video_inputs[0]     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        1,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)

														# Test batched
														lowerCamelCase__   :      int			    =			image_processor(UpperCamelCase__     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        self.image_processor_tester.batch_size,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)




							def 						lowerCamelCase_							(				self:							Dict	):
														# Initialize image_processor
														lowerCamelCase__   :      Union[str, Any]			    =			self.image_processing_class(**self.image_processor_dict	)
														# create random numpy tensors
														lowerCamelCase__   :      List[str]			    =			prepare_video_inputs(self.image_processor_tester     ,				equal_resolution=UpperCamelCase__     ,				numpify=UpperCamelCase__	)
														for video in video_inputs:
																					self.assertIsInstance(UpperCamelCase__     ,				UpperCamelCase__	)
																					self.assertIsInstance(video[0]     ,				np.ndarray	)

														# Test not batched input
														lowerCamelCase__   :      Tuple			    =			image_processor(video_inputs[0]     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        1,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)

														# Test batched
														lowerCamelCase__   :      Union[str, Any]			    =			image_processor(UpperCamelCase__     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        self.image_processor_tester.batch_size,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)




							def 						lowerCamelCase_							(				self:							Dict	):
														# Initialize image_processor
														lowerCamelCase__   :      Dict			    =			self.image_processing_class(**self.image_processor_dict	)
														# create random PyTorch tensors
														lowerCamelCase__   :      Optional[int]			    =			prepare_video_inputs(self.image_processor_tester     ,				equal_resolution=UpperCamelCase__     ,				torchify=UpperCamelCase__	)
														for video in video_inputs:
																					self.assertIsInstance(UpperCamelCase__     ,				UpperCamelCase__	)
																					self.assertIsInstance(video[0]     ,				torch.Tensor	)

														# Test not batched input
														lowerCamelCase__   :      List[str]			    =			image_processor(video_inputs[0]     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        1,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)

														# Test batched
														lowerCamelCase__   :      Any			    =			image_processor(UpperCamelCase__     ,				return_tensors="""pt"""	).pixel_values
														self.assertEqual(
														    encoded_videos.shape     ,				(
														        self.image_processor_tester.batch_size,
														        self.image_processor_tester.num_frames,
														        self.image_processor_tester.num_channels,
														        self.image_processor_tester.crop_size["""height"""],
														        self.image_processor_tester.crop_size["""width"""],
														    )     ,				)









'''simple docstring'''







from __future__ import annotations





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase ) ->			Dict:
							lowerCamelCase__   :      List[str]			    =			0
							lowerCamelCase__   :      Tuple			    =			len(UpperCamelCase ) - 1
							while left <= right:
														lowerCamelCase__   :      List[str]			    =			(left + right) // 2
														if left == right:
																					if sorted_list[middle] < item:
																												lowerCamelCase__   :      Any			    =			middle + 1
																					break
														elif sorted_list[middle] < item:
																					lowerCamelCase__   :      Optional[Any]			    =			middle + 1
														else:
																					lowerCamelCase__   :      Dict			    =			middle - 1
							sorted_list.insert(UpperCamelCase							,     UpperCamelCase )
							return sorted_list





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase ) ->			Tuple:
							lowerCamelCase__   :      Any			    =			[]
							while left and right:
														if left[0][0] < right[0][0]:
																					result.append(left.pop(0 ) )
														else:
																					result.append(right.pop(0 ) )
							return result + left + right





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase ) ->			Any:
							lowerCamelCase__   :      Optional[Any]			    =			len(UpperCamelCase )
							if length <= 1:
														return list_ad
							lowerCamelCase__   :      Tuple			    =			length // 2
							return merge(sortlist_ad(list_ad[:middle] )							,     sortlist_ad(list_ad[middle:] ) )





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase ) ->			list[int]:

							if len(UpperCamelCase ) <= 1:
														return collection
							lowerCamelCase__   :      int			    =			[]
							lowerCamelCase__   :      int			    =			False
							for i in range(0							,     len(UpperCamelCase )							,     2 ):
														if i == len(UpperCamelCase ) - 1:
																					lowerCamelCase__   :      List[Any]			    =			True
														else:
																					if collection[i] < collection[i + 1]:
																												two_paired_list.append([collection[i], collection[i + 1]] )
																					else:
																												two_paired_list.append([collection[i + 1], collection[i]] )
							lowerCamelCase__   :      List[Any]			    =			sortlist_ad(UpperCamelCase )
							lowerCamelCase__   :      List[Any]			    =			[i[0] for i in sorted_list_ad]
							result.append(sorted_list_ad[-1][1] )
							if has_last_odd_item:
														lowerCamelCase__   :      int			    =			collection[-1]
														lowerCamelCase__   :      str			    =			binary_search_insertion(UpperCamelCase							,     UpperCamelCase )
							lowerCamelCase__   :      Any			    =			False
							for i in range(len(UpperCamelCase ) - 1 ):
														if result[i] == collection[-1] and has_last_odd_item:
																					lowerCamelCase__   :      Any			    =			True
														lowerCamelCase__   :      Dict			    =			sorted_list_ad[i][1]
														# If last_odd_item is inserted before the item's index,
														# you should forward index one more.
														if is_last_odd_item_inserted_before_this_index:
																					lowerCamelCase__   :      List[str]			    =			result[: i + 2] + binary_search_insertion(result[i + 2 :]							,     UpperCamelCase )
														else:
																					lowerCamelCase__   :      Dict			    =			result[: i + 1] + binary_search_insertion(result[i + 1 :]							,     UpperCamelCase )

							return result


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

