
import unittest

from transformers import SPIECE_UNDERLINE, XLNetTokenizer, XLNetTokenizerFast
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin


_UpperCAmelCase :			Any              =	get_tests_dir("fixtures/test_sentencepiece.model")


@require_sentencepiece
@require_tokenizers
class     lowercase (		lowerCamelCase__  ,       unittest.TestCase       ):
		__lowercase	:	List[Any]     					=    XLNetTokenizer
		__lowercase	:	Tuple     					=    XLNetTokenizerFast
		__lowercase	:	int     					=    True
		__lowercase	:	List[str]     					=    True



		def __UpperCamelCase			(			self	)  -> Optional[Any]:
				"""simple docstring"""
				super().setUp()

				# We have a SentencePiece fixture for testing
				UpperCamelCase          =					XLNetTokenizer(__lowerCamelCase    ,				keep_accents=__lowerCamelCase	)
				tokenizer.sanitize_special_tokens()
				tokenizer.save_pretrained(self.tmpdirname	)



		def __UpperCamelCase			(			self	)  -> List[Any]:
				"""simple docstring"""
				UpperCamelCase          =					'''<s>'''
				UpperCamelCase          =					1

				self.assertEqual(self.get_tokenizer()._convert_token_to_id(__lowerCamelCase	)    ,				__lowerCamelCase	)
				self.assertEqual(self.get_tokenizer()._convert_id_to_token(__lowerCamelCase	)    ,				__lowerCamelCase	)



		def __UpperCamelCase			(			self	)  -> Dict:
				"""simple docstring"""
				UpperCamelCase          =					list(self.get_tokenizer().get_vocab().keys()	)

				self.assertEqual(vocab_keys[0]    ,				'<unk>'	)
				self.assertEqual(vocab_keys[1]    ,				'<s>'	)
				self.assertEqual(vocab_keys[-1]    ,				'<eod>'	)
				self.assertEqual(len(__lowerCamelCase	)    ,				1_006	)



		def __UpperCamelCase			(			self	)  -> Optional[Any]:
				"""simple docstring"""
				self.assertEqual(self.get_tokenizer().vocab_size    ,				1_000	)



		def __UpperCamelCase			(			self	)  -> Any:
				"""simple docstring"""
				UpperCamelCase          =					XLNetTokenizer(__lowerCamelCase    ,				keep_accents=__lowerCamelCase	)

				UpperCamelCase          =					tokenizer.tokenize('This is a test'	)
				self.assertListEqual(__lowerCamelCase    ,				['▁This', '▁is', '▁a', '▁t', 'est']	)

				self.assertListEqual(tokenizer.convert_tokens_to_ids(__lowerCamelCase	)    ,				[285, 46, 10, 170, 382]	)

				UpperCamelCase          =					tokenizer.tokenize('I was born in 92000, and this is falsé.'	)
				self.assertListEqual(
				    __lowerCamelCase    ,				[
				        SPIECE_UNDERLINE + 'I',
				        SPIECE_UNDERLINE + 'was',
				        SPIECE_UNDERLINE + 'b',
				        'or',
				        'n',
				        SPIECE_UNDERLINE + 'in',
				        SPIECE_UNDERLINE + '',
				        '9',
				        '2',
				        '0',
				        '0',
				        '0',
				        ',',
				        SPIECE_UNDERLINE + 'and',
				        SPIECE_UNDERLINE + 'this',
				        SPIECE_UNDERLINE + 'is',
				        SPIECE_UNDERLINE + 'f',
				        'al',
				        's',
				        'é',
				        '.',
				    ]    ,				)
				UpperCamelCase          =					tokenizer.convert_tokens_to_ids(__lowerCamelCase	)
				self.assertListEqual(__lowerCamelCase    ,				[8, 21, 84, 55, 24, 19, 7, 0, 602, 347, 347, 347, 3, 12, 66, 46, 72, 80, 6, 0, 4]	)

				UpperCamelCase          =					tokenizer.convert_ids_to_tokens(__lowerCamelCase	)
				self.assertListEqual(
				    __lowerCamelCase    ,				[
				        SPIECE_UNDERLINE + 'I',
				        SPIECE_UNDERLINE + 'was',
				        SPIECE_UNDERLINE + 'b',
				        'or',
				        'n',
				        SPIECE_UNDERLINE + 'in',
				        SPIECE_UNDERLINE + '',
				        '<unk>',
				        '2',
				        '0',
				        '0',
				        '0',
				        ',',
				        SPIECE_UNDERLINE + 'and',
				        SPIECE_UNDERLINE + 'this',
				        SPIECE_UNDERLINE + 'is',
				        SPIECE_UNDERLINE + 'f',
				        'al',
				        's',
				        '<unk>',
				        '.',
				    ]    ,				)



		def __UpperCamelCase			(			self	)  -> Optional[int]:
				"""simple docstring"""
				UpperCamelCase          =					XLNetTokenizer(__lowerCamelCase    ,				do_lower_case=__lowerCamelCase	)
				UpperCamelCase          =					tokenizer.tokenize('I was born in 92000, and this is falsé.'	)
				self.assertListEqual(
				    __lowerCamelCase    ,				[
				        SPIECE_UNDERLINE + '',
				        'i',
				        SPIECE_UNDERLINE + 'was',
				        SPIECE_UNDERLINE + 'b',
				        'or',
				        'n',
				        SPIECE_UNDERLINE + 'in',
				        SPIECE_UNDERLINE + '',
				        '9',
				        '2',
				        '0',
				        '0',
				        '0',
				        ',',
				        SPIECE_UNDERLINE + 'and',
				        SPIECE_UNDERLINE + 'this',
				        SPIECE_UNDERLINE + 'is',
				        SPIECE_UNDERLINE + 'f',
				        'al',
				        'se',
				        '.',
				    ]    ,				)
				self.assertListEqual(tokenizer.tokenize('H\u00E9llo'	)    ,				['▁he', 'll', 'o']	)



		def __UpperCamelCase			(			self	)  -> Dict:
				"""simple docstring"""
				UpperCamelCase          =					XLNetTokenizer(__lowerCamelCase    ,				do_lower_case=__lowerCamelCase	)
				UpperCamelCase          =					tokenizer.tokenize('I was born in 92000, and this is falsé.'	)
				self.assertListEqual(
				    __lowerCamelCase    ,				[
				        SPIECE_UNDERLINE + 'I',
				        SPIECE_UNDERLINE + 'was',
				        SPIECE_UNDERLINE + 'b',
				        'or',
				        'n',
				        SPIECE_UNDERLINE + 'in',
				        SPIECE_UNDERLINE + '',
				        '9',
				        '2',
				        '0',
				        '0',
				        '0',
				        ',',
				        SPIECE_UNDERLINE + 'and',
				        SPIECE_UNDERLINE + 'this',
				        SPIECE_UNDERLINE + 'is',
				        SPIECE_UNDERLINE + 'f',
				        'al',
				        'se',
				        '.',
				    ]    ,				)



		@slow
		def __UpperCamelCase			(			self	)  -> Any:
				"""simple docstring"""
				UpperCamelCase          =					XLNetTokenizer.from_pretrained('xlnet-base-cased'	)

				UpperCamelCase          =					tokenizer.encode('sequence builders'    ,				add_special_tokens=__lowerCamelCase	)
				UpperCamelCase          =					tokenizer.encode('multi-sequence build'    ,				add_special_tokens=__lowerCamelCase	)

				UpperCamelCase          =					tokenizer.build_inputs_with_special_tokens(__lowerCamelCase	)
				UpperCamelCase          =					tokenizer.build_inputs_with_special_tokens(__lowerCamelCase    ,				__lowerCamelCase	)

				assert encoded_sentence == text + [4, 3]
				assert encoded_pair == text + [4] + text_a + [4, 3]



		@slow
		def __UpperCamelCase			(			self	)  -> Union[str, Any]:
				"""simple docstring"""
				UpperCamelCase          =					{'''input_ids''': [[17, 21_442, 270, 17, 10, 14_645, 318, 34, 17, 4_546, 3_145, 787, 13, 7_752, 22_018, 23, 21, 17, 4_546, 3_145, 787, 13, 3_352, 14_431, 13, 5_500, 11, 1_176, 580, 13, 16_819, 4_797, 23, 17, 10, 17_135, 658, 19, 457, 7_932, 13, 184, 19, 3_154, 17_135, 6_468, 19, 1_404, 12_269, 19, 4_229, 5_356, 16_264, 46, 19, 17, 20_545, 10_395, 9, 9, 9, 11, 28, 6_421, 9_531, 20_729, 17, 10, 353, 17_022, 11, 21, 6_421, 9_531, 16_949, 17, 10, 11_509, 753, 11, 33, 95, 2_421, 7_385, 956, 14_431, 2_626, 25, 842, 7_385, 4_836, 21, 1_429, 2_272, 9_855, 3_120, 161, 24_738, 19, 13_203, 658, 218, 787, 21, 430, 18_482, 847, 2_637, 9, 4, 3], [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 322, 22_178, 27, 1_064, 22, 956, 13, 11_101, 1_429, 5_854, 24_313, 18_953, 40, 422, 24_366, 68, 1_758, 37, 10_483, 14_257, 31, 207, 263, 21, 203, 3_773, 25, 71, 9_735, 9, 4, 3], [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 32, 2_049, 3_442, 17, 13_894, 3_380, 23, 95, 18, 17_634, 2_288, 9, 4, 3]], '''token_type_ids''': [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]], '''attention_mask''': [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]}  # noqa: E501
				# fmt: on

				self.tokenizer_integration_test_util(
				    expected_encoding=__lowerCamelCase    ,				model_name='xlnet-base-cased'    ,				revision='c841166438c31ec7ca9a106dee7bb312b73ae511'    ,				)


from __future__ import annotations


def 				A	( lowercase   ,	lowercase   ,	lowercase   ,	lowercase			)       ->  list:
		'''simple docstring'''

		UpperCamelCase          =					[]
		UpperCamelCase     ,  UpperCamelCase          =					input_list[low:mid], input_list[mid : high + 1]
		while left and right:
				result.append((left if left[0] <= right[0] else right).pop(0			)			)
		UpperCamelCase          =					result + left + right
		return input_list


def 				A	( lowercase			)       ->  list:
		'''simple docstring'''

		if len(lowercase			) <= 1:
				return input_list
		UpperCamelCase          =					list(lowercase			)

		# iteration for two-way merging
		UpperCamelCase          =					2
		while p <= len(lowercase			):
				# getting low, high and middle value for merge-sort of single list
				for i in range(0   ,	len(lowercase			)   ,	lowercase			):
						UpperCamelCase          =					i
						UpperCamelCase          =					i + p - 1
						UpperCamelCase          =					(low + high + 1) // 2
						UpperCamelCase          =					merge(lowercase   ,	lowercase   ,	lowercase   ,	lowercase			)
				# final merge of last two parts
				if p * 2 >= len(lowercase			):
						UpperCamelCase          =					i
						UpperCamelCase          =					merge(lowercase   ,	0   ,	lowercase   ,	len(lowercase			) - 1			)
						break
				p *= 2

		return input_list


if __name__ == "__main__":
					_UpperCAmelCase :			Any              =	input("Enter numbers separated by a comma:\n").strip()
					if user_input == "":
										_UpperCAmelCase :			Optional[Any]              =	[]
					else:
										_UpperCAmelCase :			Any              =	[int(item.strip()) for item in user_input.split(",")]
					print(iter_merge_sort(unsorted))
