



'''simple docstring'''


import unittest

from parameterized import parameterized

from transformers import OpenLlamaConfig, is_torch_available, set_seed
from transformers.testing_utils import require_torch, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
   import torch

   from transformers import OpenLlamaForCausalLM, OpenLlamaForSequenceClassification, OpenLlamaModel

class  SCREAMING_SNAKE_CASE :






    """simple docstring"""





    def __init__(  self      :					Tuple  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					Tuple=1_3  ,						UpperCamelCase__      :					Any=7  ,						UpperCamelCase__      :					Optional[Any]=True  ,						UpperCamelCase__      :					List[Any]=True  ,						UpperCamelCase__      :					Optional[int]=False  ,						UpperCamelCase__      :					List[Any]=True  ,						UpperCamelCase__      :					List[Any]=9_9  ,						UpperCamelCase__      :					Dict=3_2  ,						UpperCamelCase__      :					Tuple=5  ,						UpperCamelCase__      :					str=4  ,						UpperCamelCase__      :					List[str]=3_7  ,						UpperCamelCase__      :					int="gelu"  ,						UpperCamelCase__      :					List[Any]=0.1  ,						UpperCamelCase__      :					Union[str, Any]=0.1  ,						UpperCamelCase__      :					Union[str, Any]=5_1_2  ,						UpperCamelCase__      :					Optional[Any]=1_6  ,						UpperCamelCase__      :					List[Any]=2  ,						UpperCamelCase__      :					str=0.0_2  ,						UpperCamelCase__      :					str=3  ,						UpperCamelCase__      :					Union[str, Any]=4  ,						UpperCamelCase__      :					List[str]=None  ,						):


       """simple docstring"""







       UpperCamelCase					=  parent
       UpperCamelCase					=  batch_size
       UpperCamelCase					=  seq_length
       UpperCamelCase					=  is_training
       UpperCamelCase					=  use_input_mask
       UpperCamelCase					=  use_token_type_ids
       UpperCamelCase					=  use_labels
       UpperCamelCase					=  vocab_size
       UpperCamelCase					=  hidden_size
       UpperCamelCase					=  num_hidden_layers
       UpperCamelCase					=  num_attention_heads
       UpperCamelCase					=  intermediate_size
       UpperCamelCase					=  hidden_act
       UpperCamelCase					=  hidden_dropout_prob
       UpperCamelCase					=  attention_probs_dropout_prob
       UpperCamelCase					=  max_position_embeddings
       UpperCamelCase					=  type_vocab_size
       UpperCamelCase					=  type_sequence_label_size
       UpperCamelCase					=  initializer_range
       UpperCamelCase					=  num_labels
       UpperCamelCase					=  num_choices
       UpperCamelCase					=  scope






    def  A       (  self      :					Union[str, Any] ):


       """simple docstring"""







       UpperCamelCase					=  ids_tensor([self.batch_size, self.seq_length]  ,						self.vocab_size )

       UpperCamelCase					=  None
       if self.use_input_mask:
          UpperCamelCase					=  random_attention_mask([self.batch_size, self.seq_length] )

       UpperCamelCase					=  None
       if self.use_token_type_ids:
          UpperCamelCase					=  ids_tensor([self.batch_size, self.seq_length]  ,						self.type_vocab_size )

       UpperCamelCase					=  None
       UpperCamelCase					=  None
       UpperCamelCase					=  None
       if self.use_labels:
          UpperCamelCase					=  ids_tensor([self.batch_size]  ,						self.type_sequence_label_size )
          UpperCamelCase					=  ids_tensor([self.batch_size, self.seq_length]  ,						self.num_labels )
          UpperCamelCase					=  ids_tensor([self.batch_size]  ,						self.num_choices )

       UpperCamelCase					=  self.get_config()

       return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels






    def  A       (  self      :					Optional[int] ):


       """simple docstring"""







       return OpenLlamaConfig(
           vocab_size=self.vocab_size  ,						hidden_size=self.hidden_size  ,						num_hidden_layers=self.num_hidden_layers  ,						num_attention_heads=self.num_attention_heads  ,						intermediate_size=self.intermediate_size  ,						hidden_act=self.hidden_act  ,						hidden_dropout_prob=self.hidden_dropout_prob  ,						attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,						max_position_embeddings=self.max_position_embeddings  ,						type_vocab_size=self.type_vocab_size  ,						is_decoder=UpperCamelCase__  ,						initializer_range=self.initializer_range  ,						use_stable_embedding=UpperCamelCase__  ,						)






    def  A       (  self      :					Tuple  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					int  ,						UpperCamelCase__      :					str  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					Union[str, Any]  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					Optional[Any] ):


       """simple docstring"""







       UpperCamelCase					=  OpenLlamaModel(config=UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__ )
       UpperCamelCase					=  model(UpperCamelCase__ )
       self.parent.assertEqual(result.last_hidden_state.shape  ,						(self.batch_size, self.seq_length, self.hidden_size) )






    def  A       (  self      :					List[Any]  ,						UpperCamelCase__      :					str  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					Any  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					List[Any]  ,						UpperCamelCase__      :					Tuple  ,						UpperCamelCase__      :					List[Any]  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					Union[str, Any]  ,						):


       """simple docstring"""







       UpperCamelCase					=  True
       UpperCamelCase					=  OpenLlamaModel(UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(
           UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						encoder_hidden_states=UpperCamelCase__  ,						encoder_attention_mask=UpperCamelCase__  ,						)
       UpperCamelCase					=  model(
           UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						encoder_hidden_states=UpperCamelCase__  ,						)
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__ )
       self.parent.assertEqual(result.last_hidden_state.shape  ,						(self.batch_size, self.seq_length, self.hidden_size) )






    def  A       (  self      :					List[Any]  ,						UpperCamelCase__      :					List[Any]  ,						UpperCamelCase__      :					Any  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					Union[str, Any]  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					Any  ,						UpperCamelCase__      :					str  ,						UpperCamelCase__      :					List[str]  ,						):


       """simple docstring"""







       UpperCamelCase					=  OpenLlamaForCausalLM(config=UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						labels=UpperCamelCase__ )
       self.parent.assertEqual(result.logits.shape  ,						(self.batch_size, self.seq_length, self.vocab_size) )






    def  A       (  self      :					int  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					List[Any]  ,						UpperCamelCase__      :					Tuple  ,						UpperCamelCase__      :					List[str]  ,						UpperCamelCase__      :					Optional[Any]  ,						UpperCamelCase__      :					Union[str, Any]  ,						UpperCamelCase__      :					List[Any]  ,						UpperCamelCase__      :					List[str]  ,						):


       """simple docstring"""







       UpperCamelCase					=  True
       UpperCamelCase					=  True
       UpperCamelCase					=  OpenLlamaForCausalLM(config=UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()

       # first forward pass
       UpperCamelCase					=  model(
           UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						encoder_hidden_states=UpperCamelCase__  ,						encoder_attention_mask=UpperCamelCase__  ,						use_cache=UpperCamelCase__  ,						)
       UpperCamelCase					=  outputs.past_key_values

       # create hypothetical multiple next token and extent to next_input_ids
       UpperCamelCase					=  ids_tensor((self.batch_size, 3)  ,						config.vocab_size )
       UpperCamelCase					=  ids_tensor((self.batch_size, 3)  ,						vocab_size=2 )

       # append to next input_ids and
       UpperCamelCase					=  torch.cat([input_ids, next_tokens]  ,						dim=-1 )
       UpperCamelCase					=  torch.cat([input_mask, next_mask]  ,						dim=-1 )

       UpperCamelCase					=  model(
           UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						encoder_hidden_states=UpperCamelCase__  ,						encoder_attention_mask=UpperCamelCase__  ,						output_hidden_states=UpperCamelCase__  ,						)['hidden_states'][0]
       UpperCamelCase					=  model(
           UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						encoder_hidden_states=UpperCamelCase__  ,						encoder_attention_mask=UpperCamelCase__  ,						past_key_values=UpperCamelCase__  ,						output_hidden_states=UpperCamelCase__  ,						)['hidden_states'][0]

       # select random slice
       UpperCamelCase					=  ids_tensor((1,)  ,						output_from_past.shape[-1] ).item()
       UpperCamelCase					=  output_from_no_past[:, -3:, random_slice_idx].detach()
       UpperCamelCase					=  output_from_past[:, :, random_slice_idx].detach()

       self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1] )

       # test that outputs are equal for slice
       self.parent.assertTrue(torch.allclose(UpperCamelCase__  ,						UpperCamelCase__  ,						atol=1E-3 ) )






    def  A       (  self      :					Any ):


       """simple docstring"""







       UpperCamelCase					=  self.prepare_config_and_inputs()
       (
           (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      (
           UpperCamelCase
       )				,      
       )					=  config_and_inputs
       UpperCamelCase					=  {'input_ids': input_ids, 'attention_mask': input_mask}
       return config, inputs_dict

@require_torch
class  SCREAMING_SNAKE_CASE (  _a   ,						_a   ,						_a   ,						unittest.TestCase		):






    """simple docstring"""





    _SCREAMING_SNAKE_CASE	  =  (
        (OpenLlamaModel, OpenLlamaForCausalLM, OpenLlamaForSequenceClassification) if is_torch_available() else ()
    )
    _SCREAMING_SNAKE_CASE	  =  (OpenLlamaForCausalLM,) if is_torch_available() else ()
    _SCREAMING_SNAKE_CASE	  =  (
        {
            """feature-extraction""": OpenLlamaModel,
            """text-classification""": OpenLlamaForSequenceClassification,
            """text-generation""": OpenLlamaForCausalLM,
            """zero-shot""": OpenLlamaForSequenceClassification,
        }
        if is_torch_available()
        else {}
    )
    _SCREAMING_SNAKE_CASE	  =  False
    _SCREAMING_SNAKE_CASE	  =  False






    def  A       (  self      :					str ):


       """simple docstring"""







       UpperCamelCase					=  OpenLlamaModelTester(self )
       UpperCamelCase					=  ConfigTester(self  ,						config_class=UpperCamelCase__  ,						hidden_size=3_7 )






    def  A       (  self      :					int ):


       """simple docstring"""







       self.config_tester.run_common_tests()






    def  A       (  self      :					Dict ):


       """simple docstring"""







       UpperCamelCase					=  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_model(*UpperCamelCase__ )






    def  A       (  self      :					Optional[Any] ):


       """simple docstring"""







       UpperCamelCase					=  self.model_tester.prepare_config_and_inputs()
       for type in ["absolute", "relative_key", "relative_key_query"]:
          UpperCamelCase					=  type
          self.model_tester.create_and_check_model(*UpperCamelCase__ )






    def  A       (  self      :					int ):


       """simple docstring"""







       UpperCamelCase				,      UpperCamelCase					=  self.model_tester.prepare_config_and_inputs_for_common()
       UpperCamelCase					=  3
       UpperCamelCase					=  input_dict['input_ids']
       UpperCamelCase					=  input_ids.ne(1 ).to(UpperCamelCase__ )
       UpperCamelCase					=  ids_tensor([self.model_tester.batch_size]  ,						self.model_tester.type_sequence_label_size )
       UpperCamelCase					=  OpenLlamaForSequenceClassification(UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						labels=UpperCamelCase__ )
       self.assertEqual(result.logits.shape  ,						(self.model_tester.batch_size, self.model_tester.num_labels) )






    def  A       (  self      :					List[Any] ):


       """simple docstring"""







       UpperCamelCase				,      UpperCamelCase					=  self.model_tester.prepare_config_and_inputs_for_common()
       UpperCamelCase					=  3
       UpperCamelCase					=  'single_label_classification'
       UpperCamelCase					=  input_dict['input_ids']
       UpperCamelCase					=  input_ids.ne(1 ).to(UpperCamelCase__ )
       UpperCamelCase					=  ids_tensor([self.model_tester.batch_size]  ,						self.model_tester.type_sequence_label_size )
       UpperCamelCase					=  OpenLlamaForSequenceClassification(UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						labels=UpperCamelCase__ )
       self.assertEqual(result.logits.shape  ,						(self.model_tester.batch_size, self.model_tester.num_labels) )






    def  A       (  self      :					Optional[int] ):


       """simple docstring"""







       UpperCamelCase				,      UpperCamelCase					=  self.model_tester.prepare_config_and_inputs_for_common()
       UpperCamelCase					=  3
       UpperCamelCase					=  'multi_label_classification'
       UpperCamelCase					=  input_dict['input_ids']
       UpperCamelCase					=  input_ids.ne(1 ).to(UpperCamelCase__ )
       UpperCamelCase					=  ids_tensor(
           [self.model_tester.batch_size, config.num_labels]  ,						self.model_tester.type_sequence_label_size ).to(torch.float )
       UpperCamelCase					=  OpenLlamaForSequenceClassification(UpperCamelCase__ )
       model.to(UpperCamelCase__ )
       model.eval()
       UpperCamelCase					=  model(UpperCamelCase__  ,						attention_mask=UpperCamelCase__  ,						labels=UpperCamelCase__ )
       self.assertEqual(result.logits.shape  ,						(self.model_tester.batch_size, self.model_tester.num_labels) )






    @unittest.skip('Open-Llama buffers include complex numbers, which breaks this test' )
    def  A       (  self      :					Tuple ):


       """simple docstring"""







       pass






    @parameterized.expand([('linear',), ('dynamic',)] )
    def  A       (  self      :					Union[str, Any]  ,						UpperCamelCase__      :					Any ):


       """simple docstring"""







       UpperCamelCase				,      UpperCamelCase					=  self.model_tester.prepare_config_and_inputs_for_common()
       UpperCamelCase					=  ids_tensor([1, 1_0]  ,						config.vocab_size )
       UpperCamelCase					=  ids_tensor([1, int(config.max_position_embeddings * 1.5 )]  ,						config.vocab_size )

       set_seed(4_2 )  # Fixed seed at init time so the two models get the same random weights
       UpperCamelCase					=  OpenLlamaModel(UpperCamelCase__ )
       original_model.to(UpperCamelCase__ )
       original_model.eval()
       UpperCamelCase					=  original_model(UpperCamelCase__ ).last_hidden_state
       UpperCamelCase					=  original_model(UpperCamelCase__ ).last_hidden_state

       set_seed(4_2 )  # Fixed seed at init time so the two models get the same random weights
       UpperCamelCase					=  {'type': scaling_type, 'factor': 1_0.0}
       UpperCamelCase					=  OpenLlamaModel(UpperCamelCase__ )
       scaled_model.to(UpperCamelCase__ )
       scaled_model.eval()
       UpperCamelCase					=  scaled_model(UpperCamelCase__ ).last_hidden_state
       UpperCamelCase					=  scaled_model(UpperCamelCase__ ).last_hidden_state

       # Dynamic scaling does not change the RoPE embeddings until it receives an input longer than the original
       # maximum sequence length, so the outputs for the short input should match.
       if scaling_type == "dynamic":
          self.assertTrue(torch.allclose(UpperCamelCase__  ,						UpperCamelCase__  ,						atol=1E-5 ) )
       else:
          self.assertFalse(torch.allclose(UpperCamelCase__  ,						UpperCamelCase__  ,						atol=1E-5 ) )

       # The output should be different for long inputs
       self.assertFalse(torch.allclose(UpperCamelCase__  ,						UpperCamelCase__  ,						atol=1E-5 ) )






'''simple docstring'''


def 				__lowerCamelCase				(   A__    )       ->	list:






   """simple docstring"""
   UpperCamelCase					=  len(A__    )
   for i in range(1    ,						A__    ):
      UpperCamelCase					=  collection[i]
      UpperCamelCase					=  0
      UpperCamelCase					=  i - 1

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


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

