





import os
import sys
import tempfile
import unittest
import unittest.mock as mock
from pathlib import Path

from huggingface_hub import HfFolder, delete_repo
from huggingface_hub.file_download import http_get
from requests.exceptions import HTTPError

from transformers import (
    AlbertTokenizer,
    AutoTokenizer,
    BertTokenizer,
    BertTokenizerFast,
    GPTaTokenizerFast,
    is_tokenizers_available,
)
from transformers.testing_utils import TOKEN, USER, is_staging_test, require_tokenizers
from transformers.tokenization_utils import Trie


sys.path.append(str(Path(__file__).parent.parent / "utils"))

from test_module.custom_tokenization import CustomTokenizer  # noqa E402


if is_tokenizers_available():
   from test_module.custom_tokenization_fast import CustomTokenizerFast

class 					A     (unittest.TestCase					):



      def  __a			(       self       )   -> int:



             '''simple docstring'''

             _snake_case   :				List[Any]  					=    mock.Mock()
             _snake_case   :				Optional[int]  					=    500
             _snake_case   :				Any  					=    {}
             _snake_case   :				Tuple  					=    HTTPError
             _snake_case   :				Optional[Any]  					=    {}

             # Download this model to make sure it's in the cache.
             _snake_case   :				Tuple  					=    BertTokenizer.from_pretrained('''hf-internal-testing/tiny-random-bert'''       )

             # Under the mock environment we get a 500 error when trying to reach the tokenizer.
             with mock.patch('''requests.Session.request'''  ,	return_value=lowerCamelCase__       ) as mock_head:
                    _snake_case   :				Dict  					=    BertTokenizer.from_pretrained('''hf-internal-testing/tiny-random-bert'''       )
                    # This check we did call the fake head request
                    mock_head.assert_called()



      @require_tokenizers
      def  __a			(       self       )   -> Union[str, Any]:



             '''simple docstring'''

             _snake_case   :				int  					=    mock.Mock()
             _snake_case   :				str  					=    500
             _snake_case   :				Dict  					=    {}
             _snake_case   :				List[Any]  					=    HTTPError
             _snake_case   :				Dict  					=    {}

             # Download this model to make sure it's in the cache.
             _snake_case   :				Optional[int]  					=    GPTaTokenizerFast.from_pretrained('''gpt2'''       )

             # Under the mock environment we get a 500 error when trying to reach the tokenizer.
             with mock.patch('''requests.Session.request'''  ,	return_value=lowerCamelCase__       ) as mock_head:
                    _snake_case   :				Any  					=    GPTaTokenizerFast.from_pretrained('''gpt2'''       )
                    # This check we did call the fake head request
                    mock_head.assert_called()



      def  __a			(       self       )   -> Union[str, Any]:



             '''simple docstring'''

             try:
                    _snake_case   :				Any  					=    tempfile.mktemp()
                    with open(lowerCamelCase__  ,	'''wb'''       ) as f:
                           http_get('''https://huggingface.co/albert-base-v1/resolve/main/spiece.model'''  ,	lowerCamelCase__       )

                    _snake_case   :				int  					=    AlbertTokenizer.from_pretrained(lowerCamelCase__       )
             finally:
                    os.remove(lowerCamelCase__       )

             # Supporting this legacy load introduced a weird bug where the tokenizer would load local files if they are in
             # the current folder and have the right name.
             if os.path.isfile('''tokenizer.json'''       ):
                    # We skip the test if the user has a `tokenizer.json` in this folder to avoid deleting it.
                    return
             try:
                    with open('''tokenizer.json'''  ,	'''wb'''       ) as f:
                           http_get('''https://huggingface.co/hf-internal-testing/tiny-random-bert/blob/main/tokenizer.json'''  ,	lowerCamelCase__       )
                    _snake_case   :				Optional[int]  					=    AutoTokenizer.from_pretrained('''hf-internal-testing/tiny-random-gpt2'''       )
                    # The tiny random BERT has a vocab size of 1024, tiny gpt2 as a vocab size of 1000
                    self.assertEqual(tokenizer.vocab_size  ,	1000       )
                    # Tokenizer should depend on the remote checkpoint, not the local tokenizer.json file.

             finally:
                    os.remove('''tokenizer.json'''       )



      def  __a			(       self       )   -> List[str]:



             '''simple docstring'''

             _snake_case   :				Optional[int]  					=    AlbertTokenizer.from_pretrained('''https://huggingface.co/albert-base-v1/resolve/main/spiece.model'''       )


@is_staging_test
class 					A     (unittest.TestCase					):
      _SCREAMING_SNAKE_CASE       =				["""[UNK]""", """[CLS]""", """[SEP]""", """[PAD]""", """[MASK]""", """bla""", """blou"""]



      @classmethod
      def  __a			(       cls       )   -> Tuple:



             '''simple docstring'''

             _snake_case   :				List[Any]  					=    TOKEN
             HfFolder.save_token(lowerCamelCase__       )



      @classmethod
      def  __a			(       cls       )   -> Dict:



             '''simple docstring'''

             try:
                    delete_repo(token=cls._token  ,	repo_id='''test-tokenizer'''       )
             except HTTPError:
                    pass

             try:
                    delete_repo(token=cls._token  ,	repo_id='''valid_org/test-tokenizer-org'''       )
             except HTTPError:
                    pass

             try:
                    delete_repo(token=cls._token  ,	repo_id='''test-dynamic-tokenizer'''       )
             except HTTPError:
                    pass



      def  __a			(       self       )   -> Optional[Any]:



             '''simple docstring'''

             with tempfile.TemporaryDirectory() as tmp_dir:
                    _snake_case   :				int  					=    os.path.join(lowerCamelCase__  ,	'''vocab.txt'''       )
                    with open(lowerCamelCase__  ,	'''w'''  ,	encoding='''utf-8'''       ) as vocab_writer:
                           vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]       )       )
                    _snake_case   :				int  					=    BertTokenizer(lowerCamelCase__       )

             tokenizer.push_to_hub('''test-tokenizer'''  ,	use_auth_token=self._token       )
             _snake_case   :				Tuple  					=    BertTokenizer.from_pretrained(F'''{USER}/test-tokenizer'''       )
             self.assertDictEqual(new_tokenizer.vocab  ,	tokenizer.vocab       )

             # Reset repo
             delete_repo(token=self._token  ,	repo_id='''test-tokenizer'''       )

             # Push to hub via save_pretrained
             with tempfile.TemporaryDirectory() as tmp_dir:
                    tokenizer.save_pretrained(lowerCamelCase__  ,	repo_id='''test-tokenizer'''  ,	push_to_hub=lowerCamelCase__  ,	use_auth_token=self._token       )

             _snake_case   :				Dict  					=    BertTokenizer.from_pretrained(F'''{USER}/test-tokenizer'''       )
             self.assertDictEqual(new_tokenizer.vocab  ,	tokenizer.vocab       )



      def  __a			(       self       )   -> Tuple:



             '''simple docstring'''

             with tempfile.TemporaryDirectory() as tmp_dir:
                    _snake_case   :				Union[str, Any]  					=    os.path.join(lowerCamelCase__  ,	'''vocab.txt'''       )
                    with open(lowerCamelCase__  ,	'''w'''  ,	encoding='''utf-8'''       ) as vocab_writer:
                           vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]       )       )
                    _snake_case   :				Dict  					=    BertTokenizer(lowerCamelCase__       )

             tokenizer.push_to_hub('''valid_org/test-tokenizer-org'''  ,	use_auth_token=self._token       )
             _snake_case   :				Optional[int]  					=    BertTokenizer.from_pretrained('''valid_org/test-tokenizer-org'''       )
             self.assertDictEqual(new_tokenizer.vocab  ,	tokenizer.vocab       )

             # Reset repo
             delete_repo(token=self._token  ,	repo_id='''valid_org/test-tokenizer-org'''       )

             # Push to hub via save_pretrained
             with tempfile.TemporaryDirectory() as tmp_dir:
                    tokenizer.save_pretrained(
                        lowerCamelCase__  ,	repo_id='''valid_org/test-tokenizer-org'''  ,	push_to_hub=lowerCamelCase__  ,	use_auth_token=self._token       )

             _snake_case   :				List[str]  					=    BertTokenizer.from_pretrained('''valid_org/test-tokenizer-org'''       )
             self.assertDictEqual(new_tokenizer.vocab  ,	tokenizer.vocab       )



      @require_tokenizers
      def  __a			(       self       )   -> List[Any]:



             '''simple docstring'''

             CustomTokenizer.register_for_auto_class()
             with tempfile.TemporaryDirectory() as tmp_dir:
                    _snake_case   :				int  					=    os.path.join(lowerCamelCase__  ,	'''vocab.txt'''       )
                    with open(lowerCamelCase__  ,	'''w'''  ,	encoding='''utf-8'''       ) as vocab_writer:
                           vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]       )       )
                    _snake_case   :				Optional[int]  					=    CustomTokenizer(lowerCamelCase__       )

             # No fast custom tokenizer
             tokenizer.push_to_hub('''test-dynamic-tokenizer'''  ,	use_auth_token=self._token       )

             _snake_case   :				Union[str, Any]  					=    AutoTokenizer.from_pretrained(F'''{USER}/test-dynamic-tokenizer'''  ,	trust_remote_code=lowerCamelCase__       )
             # Can't make an isinstance check because the new_model.config is from the CustomTokenizer class of a dynamic module
             self.assertEqual(tokenizer.__class__.__name__  ,	'''CustomTokenizer'''       )

             # Fast and slow custom tokenizer
             CustomTokenizerFast.register_for_auto_class()
             with tempfile.TemporaryDirectory() as tmp_dir:
                    _snake_case   :				Tuple  					=    os.path.join(lowerCamelCase__  ,	'''vocab.txt'''       )
                    with open(lowerCamelCase__  ,	'''w'''  ,	encoding='''utf-8'''       ) as vocab_writer:
                           vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]       )       )

                    _snake_case   :				Tuple  					=    BertTokenizerFast.from_pretrained(lowerCamelCase__       )
                    bert_tokenizer.save_pretrained(lowerCamelCase__       )
                    _snake_case   :				Optional[Any]  					=    CustomTokenizerFast.from_pretrained(lowerCamelCase__       )

             tokenizer.push_to_hub('''test-dynamic-tokenizer'''  ,	use_auth_token=self._token       )

             _snake_case   :				Optional[Any]  					=    AutoTokenizer.from_pretrained(F'''{USER}/test-dynamic-tokenizer'''  ,	trust_remote_code=lowerCamelCase__       )
             # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
             self.assertEqual(tokenizer.__class__.__name__  ,	'''CustomTokenizerFast'''       )
             _snake_case   :				int  					=    AutoTokenizer.from_pretrained(
                 F'''{USER}/test-dynamic-tokenizer'''  ,	use_fast=lowerCamelCase__  ,	trust_remote_code=lowerCamelCase__       )
             # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
             self.assertEqual(tokenizer.__class__.__name__  ,	'''CustomTokenizer'''       )


class 					A     (unittest.TestCase					):



      def  __a			(       self       )   -> Optional[Any]:



             '''simple docstring'''

             _snake_case   :				int  					=    Trie()
             trie.add('''Hello 友達'''       )
             self.assertEqual(trie.data  ,	{'''H''': {'''e''': {'''l''': {'''l''': {'''o''': {''' ''': {'''友''': {'''達''': {'''''': 1}}}}}}}}}       )
             trie.add('''Hello'''       )
             trie.data
             self.assertEqual(trie.data  ,	{'''H''': {'''e''': {'''l''': {'''l''': {'''o''': {'''''': 1, ''' ''': {'''友''': {'''達''': {'''''': 1}}}}}}}}}       )



      def  __a			(       self       )   -> Union[str, Any]:



             '''simple docstring'''

             _snake_case   :				List[str]  					=    Trie()
             self.assertEqual(trie.split('''[CLS] This is a extra_id_100'''       )  ,	['''[CLS] This is a extra_id_100''']       )
             trie.add('''[CLS]'''       )
             trie.add('''extra_id_1'''       )
             trie.add('''extra_id_100'''       )
             self.assertEqual(trie.split('''[CLS] This is a extra_id_100'''       )  ,	['''[CLS]''', ''' This is a ''', '''extra_id_100''']       )



      def  __a			(       self       )   -> str:



             '''simple docstring'''

             _snake_case   :				Optional[Any]  					=    Trie()
             trie.add('''A'''       )
             self.assertEqual(trie.split('''ABC'''       )  ,	['''A''', '''BC''']       )
             self.assertEqual(trie.split('''BCA'''       )  ,	['''BC''', '''A''']       )



      def  __a			(       self       )   -> Tuple:



             '''simple docstring'''

             _snake_case   :				Any  					=    Trie()
             trie.add('''TOKEN]'''       )
             trie.add('''[SPECIAL_TOKEN]'''       )
             self.assertEqual(trie.split('''This is something [SPECIAL_TOKEN]'''       )  ,	['''This is something ''', '''[SPECIAL_TOKEN]''']       )



      def  __a			(       self       )   -> Tuple:



             '''simple docstring'''

             _snake_case   :				Dict  					=    Trie()
             trie.add('''A'''       )
             trie.add('''P'''       )
             trie.add('''[SPECIAL_TOKEN]'''       )
             self.assertEqual(trie.split('''This is something [SPECIAL_TOKEN]'''       )  ,	['''This is something ''', '''[SPECIAL_TOKEN]''']       )



      def  __a			(       self       )   -> int:



             '''simple docstring'''

             _snake_case   :				int  					=    Trie()
             trie.add('''AB'''       )
             trie.add('''B'''       )
             trie.add('''C'''       )
             self.assertEqual(trie.split('''ABC'''       )  ,	['''AB''', '''C''']       )



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



             '''simple docstring'''

             _snake_case   :				Optional[int]  					=    Trie()
             trie.add('''ABC'''       )
             trie.add('''B'''       )
             trie.add('''CD'''       )
             self.assertEqual(trie.split('''ABCD'''       )  ,	['''ABC''', '''D''']       )



      def  __a			(       self       )   -> List[str]:



             '''simple docstring'''

             _snake_case   :				List[Any]  					=    Trie()
             _snake_case   :				Dict  					=    trie.cut_text('''ABC'''  ,	[0, 0, 2, 1, 2, 3]       )
             self.assertEqual(lowerCamelCase__  ,	['''AB''', '''C''']       )









def 			_A	(      SCREAMING_SNAKE_CASE      ):
	UpperCAmelCase__							,						UpperCAmelCase__:	int									= [], []
	while len(SCREAMING_SNAKE_CASE      ) > 1:
		UpperCAmelCase__							,						UpperCAmelCase__:	str									= min(SCREAMING_SNAKE_CASE      ), max(SCREAMING_SNAKE_CASE      )
		start.append(SCREAMING_SNAKE_CASE      )
		end.append(SCREAMING_SNAKE_CASE      )
		collection.remove(SCREAMING_SNAKE_CASE      )
		collection.remove(SCREAMING_SNAKE_CASE      )
	end.reverse()
	return start + collection + end


if __name__ == "__main__":
					_lowerCAmelCase  :      Union[str, Any]			 =input("""Enter numbers separated by a comma:\n""").strip()
					_lowerCAmelCase  :      Dict			 =[int(item) for item in user_input.split(""",""")]
					print(*merge_sort(unsorted), sep=""",""")