
"""simple docstring"""







import shutil
import tempfile
import unittest

from transformers import SPIECE_UNDERLINE, BatchEncoding, MBartaaTokenizer, MBartaaTokenizerFast, is_torch_available
from transformers.testing_utils import (
    get_tests_dir,
    nested_simplify,
    require_sentencepiece,
    require_tokenizers,
    require_torch,
    slow,
)

from ...test_tokenization_common import TokenizerTesterMixin


_SCREAMING_SNAKE_CASE	       =      get_tests_dir("""fixtures/test_sentencepiece.model""")

if is_torch_available():
		from transformers.models.mbart.modeling_mbart import shift_tokens_right

_SCREAMING_SNAKE_CASE	       =      250_004
_SCREAMING_SNAKE_CASE	       =      250_020







@require_sentencepiece
@require_tokenizers
class 							__magic_name__     (		_snake_case      ,		unittest.TestCase   ):
					_SCREAMING_SNAKE_CASE       :					Optional[int]     							=   MBartaaTokenizer
					_SCREAMING_SNAKE_CASE       :					Optional[Any]     							=   MBartaaTokenizerFast
					_SCREAMING_SNAKE_CASE       :					Optional[Any]     							=   True
					_SCREAMING_SNAKE_CASE       :					Dict     							=   True





					def 							lowerCAmelCase      (				self   :							int    ):
												super().setUp()

												# We have a SentencePiece fixture for testing
												__snake_case     			=       MBartaaTokenizer(snake_case_							,						src_lang="en_XX"							,						tgt_lang="ro_RO"							,						keep_accents=snake_case_    )
												tokenizer.save_pretrained(self.tmpdirname    )





					def 							lowerCAmelCase      (				self   :							Dict    ):
												__snake_case     			=       "<s>"
												__snake_case     			=       0

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





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												__snake_case     			=       list(self.get_tokenizer().get_vocab().keys()    )

												self.assertEqual(vocab_keys[0]							,						"<s>"    )
												self.assertEqual(vocab_keys[1]							,						"<pad>"    )
												self.assertEqual(vocab_keys[-1]							,						"<mask>"    )
												self.assertEqual(len(snake_case_    )							,						1054    )





					def 							lowerCAmelCase      (				self   :							str    ):
												self.assertEqual(self.get_tokenizer().vocab_size							,						1054    )





					def 							lowerCAmelCase      (				self   :							List[Any]    ):
												__snake_case     			=       MBartaaTokenizer(snake_case_							,						src_lang="en_XX"							,						tgt_lang="ro_RO"							,						keep_accents=snake_case_    )

												__snake_case     			=       tokenizer.tokenize("This is a test"    )
												self.assertListEqual(snake_case_							,						["▁This", "▁is", "▁a", "▁t", "est"]    )

												self.assertListEqual(
												    tokenizer.convert_tokens_to_ids(snake_case_    )							,						[value + tokenizer.fairseq_offset for value in [285, 46, 10, 170, 382]]							,						)

												__snake_case     			=       tokenizer.tokenize("I was born in 92000, and this is falsé."    )
												self.assertListEqual(
												    snake_case_							,						[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", "é", "."]							,						)
												__snake_case     			=       tokenizer.convert_tokens_to_ids(snake_case_    )
												self.assertListEqual(
												    snake_case_							,						[
												        value + tokenizer.fairseq_offset
												        for value in [8, 21, 84, 55, 24, 19, 7, 2, 602, 347, 347, 347, 3, 12, 66, 46, 72, 80, 6, 2, 4]
												    ]							,						)

												__snake_case     			=       tokenizer.convert_ids_to_tokens(snake_case_    )
												self.assertListEqual(
												    snake_case_							,						[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>", "."]							,						)





					@slow
					def 							lowerCAmelCase      (				self   :							Optional[Any]    ):
												__snake_case     			=       {"input_ids": [[250004, 11062, 82772, 7, 15, 82772, 538, 51529, 237, 17198, 1290, 206, 9, 215175, 1314, 136, 17198, 1290, 206, 9, 56359, 42, 122009, 9, 16466, 16, 87344, 4537, 9, 4717, 78381, 6, 159958, 7, 15, 24480, 618, 4, 527, 22693, 5428, 4, 2777, 24480, 9874, 4, 43523, 594, 4, 803, 18392, 33189, 18, 4, 43523, 24447, 12399, 100, 24955, 83658, 9626, 144057, 15, 839, 22335, 16, 136, 24955, 83658, 83479, 15, 39102, 724, 16, 678, 645, 2789, 1328, 4589, 42, 122009, 115774, 23, 805, 1328, 46876, 7, 136, 53894, 1940, 42227, 41159, 17721, 823, 425, 4, 27512, 98722, 206, 136, 5531, 4970, 919, 17336, 5, 2], [250004, 20080, 618, 83, 82775, 47, 479, 9, 1517, 73, 53894, 333, 80581, 110117, 18811, 5256, 1295, 51, 152526, 297, 7986, 390, 124416, 538, 35431, 214, 98, 15044, 25737, 136, 7108, 43701, 23, 756, 135355, 7, 5, 2, 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], [250004, 581, 63773, 119455, 6, 147797, 88203, 7, 645, 70, 21, 3285, 10269, 5, 2, 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]], "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, 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], [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]]}  # noqa: E501
												# fmt: on

												self.tokenizer_integration_test_util(
												    expected_encoding=snake_case_							,						model_name="facebook/mbart-large-50"							,						revision="d3913889c59cd5c9e456b269c376325eabad57e2"							,						)





					def 							lowerCAmelCase      (				self   :							Tuple    ):

												if not self.test_slow_tokenizer:
																			# as we don't have a slow version, we can't compare the outputs between slow and fast versions
																			return

												__snake_case     			=       (self.rust_tokenizer_class, "hf-internal-testing/tiny-random-mbart50", {})
												for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
																			with self.subTest(F'''{tokenizer.__class__.__name__} ({pretrained_name})'''    ):
																										__snake_case     			=       self.rust_tokenizer_class.from_pretrained(snake_case_							,						**snake_case_    )
																										__snake_case     			=       self.tokenizer_class.from_pretrained(snake_case_							,						**snake_case_    )

																										__snake_case     			=       tempfile.mkdtemp()

																										__snake_case     			=       tokenizer_r.save_pretrained(snake_case_    )
																										__snake_case     			=       tokenizer_p.save_pretrained(snake_case_    )

																										# Checks it save with the same files + the tokenizer.json file for the fast one
																										self.assertTrue(any("tokenizer.json" in f for f in tokenizer_r_files    )    )
																										__snake_case     			=       tuple(f for f in tokenizer_r_files if "tokenizer.json" not in f    )
																										self.assertSequenceEqual(snake_case_							,						snake_case_    )

																										# Checks everything loads correctly in the same way
																										__snake_case     			=       tokenizer_r.from_pretrained(snake_case_    )
																										__snake_case     			=       tokenizer_p.from_pretrained(snake_case_    )

																										# Check special tokens are set accordingly on Rust and Python
																										for key in tokenizer_pp.special_tokens_map:
																																	self.assertTrue(hasattr(snake_case_							,						snake_case_    )    )
																																	# self.assertEqual(getattr(tokenizer_rp, key), getattr(tokenizer_pp, key))
																																	# self.assertEqual(getattr(tokenizer_rp, key + "_id"), getattr(tokenizer_pp, key + "_id"))

																										shutil.rmtree(snake_case_    )

																										# Save tokenizer rust, legacy_format=True
																										__snake_case     			=       tempfile.mkdtemp()

																										__snake_case     			=       tokenizer_r.save_pretrained(snake_case_							,						legacy_format=snake_case_    )
																										__snake_case     			=       tokenizer_p.save_pretrained(snake_case_    )

																										# Checks it save with the same files
																										self.assertSequenceEqual(snake_case_							,						snake_case_    )

																										# Checks everything loads correctly in the same way
																										__snake_case     			=       tokenizer_r.from_pretrained(snake_case_    )
																										__snake_case     			=       tokenizer_p.from_pretrained(snake_case_    )

																										# Check special tokens are set accordingly on Rust and Python
																										for key in tokenizer_pp.special_tokens_map:
																																	self.assertTrue(hasattr(snake_case_							,						snake_case_    )    )

																										shutil.rmtree(snake_case_    )

																										# Save tokenizer rust, legacy_format=False
																										__snake_case     			=       tempfile.mkdtemp()

																										__snake_case     			=       tokenizer_r.save_pretrained(snake_case_							,						legacy_format=snake_case_    )
																										__snake_case     			=       tokenizer_p.save_pretrained(snake_case_    )

																										# Checks it saved the tokenizer.json file
																										self.assertTrue(any("tokenizer.json" in f for f in tokenizer_r_files    )    )

																										# Checks everything loads correctly in the same way
																										__snake_case     			=       tokenizer_r.from_pretrained(snake_case_    )
																										__snake_case     			=       tokenizer_p.from_pretrained(snake_case_    )

																										# Check special tokens are set accordingly on Rust and Python
																										for key in tokenizer_pp.special_tokens_map:
																																	self.assertTrue(hasattr(snake_case_							,						snake_case_    )    )

																										shutil.rmtree(snake_case_    )







@require_torch
@require_sentencepiece
@require_tokenizers
class 							__magic_name__     (		unittest.TestCase   ):
					_SCREAMING_SNAKE_CASE       :					str     							=   'facebook/mbart-large-50-one-to-many-mmt'
					_SCREAMING_SNAKE_CASE       :					Optional[Any]     							=   [
					    ' UN Chief Says There Is No Military Solution in Syria',
					    ' Secretary-General Ban Ki-moon says his response to Russia\'s stepped up military support for Syria is that "there is no military solution" to the nearly five-year conflict and more weapons will only worsen the violence and misery for millions of people.',
					]
					_SCREAMING_SNAKE_CASE       :					Union[str, Any]     							=   [
					    'Şeful ONU declară că nu există o soluţie militară în Siria',
					    'Secretarul General Ban Ki-moon declară că răspunsul său la intensificarea sprijinului militar al Rusiei'
					    ' pentru Siria este că "nu există o soluţie militară" la conflictul de aproape cinci ani şi că noi arme nu vor'
					    ' face decât să înrăutăţească violenţele şi mizeria pentru milioane de oameni.',
					]
					_SCREAMING_SNAKE_CASE       :					Tuple     							=   [EN_CODE, 8274, 12_7873, 2_5916, 7, 8622, 2071, 438, 6_7485, 53, 18_7895, 23, 5_1712, 2]





					@classmethod
					def 							lowerCAmelCase      (				cls   :							List[str]    ):
												__snake_case     			=       MBartaaTokenizer.from_pretrained(
												    cls.checkpoint_name							,						src_lang="en_XX"							,						tgt_lang="ro_RO"    )
												__snake_case     			=       1
												return cls





					def 							lowerCAmelCase      (				self   :							Tuple    ):
												self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["ar_AR"]							,						250001    )
												self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["en_EN"]							,						250004    )
												self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["ro_RO"]							,						250020    )
												self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["mr_IN"]							,						250038    )





					def 							lowerCAmelCase      (				self   :							List[str]    ):
												__snake_case     			=       self.tokenizer.batch_encode_plus(self.src_text    ).input_ids[0]
												self.assertListEqual(self.expected_src_tokens							,						snake_case_    )





					def 							lowerCAmelCase      (				self   :							Dict    ):
												self.assertIn(snake_case_							,						self.tokenizer.all_special_ids    )
												__snake_case     			=       [RO_CODE, 884, 9019, 96, 9, 916, 86792, 36, 18743, 15596, 5, 2]
												__snake_case     			=       self.tokenizer.decode(snake_case_							,						skip_special_tokens=snake_case_    )
												__snake_case     			=       self.tokenizer.decode(generated_ids[1:]							,						skip_special_tokens=snake_case_    )
												self.assertEqual(snake_case_							,						snake_case_    )
												self.assertNotIn(self.tokenizer.eos_token							,						snake_case_    )





					def 							lowerCAmelCase      (				self   :							str    ):
												__snake_case     			=       ["this is gunna be a long sentence " * 20]
												assert isinstance(src_text[0]							,						snake_case_    )
												__snake_case     			=       10
												__snake_case     			=       self.tokenizer(snake_case_							,						max_length=snake_case_							,						truncation=snake_case_    ).input_ids[0]
												self.assertEqual(ids[0]							,						snake_case_    )
												self.assertEqual(ids[-1]							,						2    )
												self.assertEqual(len(snake_case_    )							,						snake_case_    )





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												self.assertListEqual(self.tokenizer.convert_tokens_to_ids(["<mask>", "ar_AR"]    )							,						[250053, 250001]    )





					def 							lowerCAmelCase      (				self   :							Optional[Any]    ):
												__snake_case     			=       tempfile.mkdtemp()
												__snake_case     			=       self.tokenizer.fairseq_tokens_to_ids
												self.tokenizer.save_pretrained(snake_case_    )
												__snake_case     			=       MBartaaTokenizer.from_pretrained(snake_case_    )
												self.assertDictEqual(new_tok.fairseq_tokens_to_ids							,						snake_case_    )





					@require_torch
					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       self.tokenizer(self.src_text							,						text_target=self.tgt_text							,						padding=snake_case_							,						return_tensors="pt"    )
												__snake_case     			=       shift_tokens_right(batch["labels"]							,						self.tokenizer.pad_token_id    )

												# fairseq batch: https://gist.github.com/sshleifer/cba08bc2109361a74ac3760a7e30e4f4
												assert batch.input_ids[1][0] == EN_CODE
												assert batch.input_ids[1][-1] == 2
												assert batch.labels[1][0] == RO_CODE
												assert batch.labels[1][-1] == 2
												assert batch.decoder_input_ids[1][:2].tolist() == [2, RO_CODE]





					@require_torch
					def 							lowerCAmelCase      (				self   :							List[str]    ):
												__snake_case     			=       self.tokenizer(
												    self.src_text							,						text_target=self.tgt_text							,						padding=snake_case_							,						truncation=snake_case_							,						max_length=len(self.expected_src_tokens    )							,						return_tensors="pt"							,						)
												__snake_case     			=       shift_tokens_right(batch["labels"]							,						self.tokenizer.pad_token_id    )

												self.assertIsInstance(snake_case_							,						snake_case_    )

												self.assertEqual((2, 14)							,						batch.input_ids.shape    )
												self.assertEqual((2, 14)							,						batch.attention_mask.shape    )
												__snake_case     			=       batch.input_ids.tolist()[0]
												self.assertListEqual(self.expected_src_tokens							,						snake_case_    )
												self.assertEqual(2							,						batch.decoder_input_ids[0, 0]    )  # decoder_start_token_id
												# Test that special tokens are reset
												self.assertEqual(self.tokenizer.prefix_tokens							,						[EN_CODE]    )
												self.assertEqual(self.tokenizer.suffix_tokens							,						[self.tokenizer.eos_token_id]    )





					def 							lowerCAmelCase      (				self   :							List[Any]    ):
												__snake_case     			=       self.tokenizer(self.src_text							,						padding=snake_case_							,						truncation=snake_case_							,						max_length=3							,						return_tensors="pt"    )
												__snake_case     			=       self.tokenizer(
												    text_target=self.tgt_text							,						padding=snake_case_							,						truncation=snake_case_							,						max_length=10							,						return_tensors="pt"    )
												__snake_case     			=       targets["input_ids"]
												__snake_case     			=       shift_tokens_right(snake_case_							,						self.tokenizer.pad_token_id    )

												self.assertEqual(batch.input_ids.shape[1]							,						3    )
												self.assertEqual(batch.decoder_input_ids.shape[1]							,						10    )





					@require_torch
					def 							lowerCAmelCase      (				self   :							List[str]    ):
												__snake_case     			=       self.tokenizer._build_translation_inputs(
												    "A test"							,						return_tensors="pt"							,						src_lang="en_XX"							,						tgt_lang="ar_AR"    )

												self.assertEqual(
												    nested_simplify(snake_case_    )							,						{
												        # en_XX, A, test, EOS
												        "input_ids": [[250004, 62, 3034, 2]],
												        "attention_mask": [[1, 1, 1, 1]],
												        # ar_AR
												        "forced_bos_token_id": 250001,
												    }							,						)


"""simple docstring"""







def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     list:







							"""simple docstring"""


							__snake_case     			=       len(SCREAMING_SNAKE_CASE )
							for i in range(1							,    SCREAMING_SNAKE_CASE ):
														__snake_case     			=       collection[i]
														__snake_case     			=       0
														__snake_case     			=       i - 1

														while low <= high:
																					__snake_case     			=       (low + high) // 2
																					if val < collection[mid]:
																												__snake_case     			=       mid - 1
																					else:
																												__snake_case     			=       mid + 1
														for j in range(SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    -1 ):
																					__snake_case     			=       collection[j - 1]
														__snake_case     			=       val
							return collection


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