


from typing import TYPE_CHECKING

from ..utils import OptionalDependencyNotAvailable, _LazyModule, is_flax_available, is_tf_available, is_torch_available


UpperCamelCase :				Union[str, Any]						    =       {
    '''configuration_utils''': ['''GenerationConfig'''],
    '''streamers''': ['''TextIteratorStreamer''', '''TextStreamer'''],
}

try:
     if not is_torch_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCamelCase :				Tuple						    =       [
         '''Constraint''',
         '''ConstraintListState''',
         '''DisjunctiveConstraint''',
         '''PhrasalConstraint''',
     ]
     UpperCamelCase :				List[str]						    =       [
         '''BeamHypotheses''',
         '''BeamScorer''',
         '''BeamSearchScorer''',
         '''ConstrainedBeamSearchScorer''',
     ]
     UpperCamelCase :				List[Any]						    =       [
         '''EpsilonLogitsWarper''',
         '''EtaLogitsWarper''',
         '''ForcedBOSTokenLogitsProcessor''',
         '''ForcedEOSTokenLogitsProcessor''',
         '''HammingDiversityLogitsProcessor''',
         '''InfNanRemoveLogitsProcessor''',
         '''LogitsProcessor''',
         '''LogitsProcessorList''',
         '''LogitsWarper''',
         '''MinLengthLogitsProcessor''',
         '''MinNewTokensLengthLogitsProcessor''',
         '''NoBadWordsLogitsProcessor''',
         '''NoRepeatNGramLogitsProcessor''',
         '''PrefixConstrainedLogitsProcessor''',
         '''RepetitionPenaltyLogitsProcessor''',
         '''SequenceBiasLogitsProcessor''',
         '''EncoderRepetitionPenaltyLogitsProcessor''',
         '''TemperatureLogitsWarper''',
         '''TopKLogitsWarper''',
         '''TopPLogitsWarper''',
         '''TypicalLogitsWarper''',
         '''EncoderNoRepeatNGramLogitsProcessor''',
         '''ExponentialDecayLengthPenalty''',
         '''LogitNormalization''',
     ]
     UpperCamelCase :				Optional[int]						    =       [
         '''MaxNewTokensCriteria''',
         '''MaxLengthCriteria''',
         '''MaxTimeCriteria''',
         '''StoppingCriteria''',
         '''StoppingCriteriaList''',
         '''validate_stopping_criteria''',
     ]
     UpperCamelCase :				Dict						    =       [
         '''GenerationMixin''',
         '''top_k_top_p_filtering''',
         '''GreedySearchEncoderDecoderOutput''',
         '''GreedySearchDecoderOnlyOutput''',
         '''SampleEncoderDecoderOutput''',
         '''SampleDecoderOnlyOutput''',
         '''BeamSearchEncoderDecoderOutput''',
         '''BeamSearchDecoderOnlyOutput''',
         '''BeamSampleEncoderDecoderOutput''',
         '''BeamSampleDecoderOnlyOutput''',
         '''ContrastiveSearchEncoderDecoderOutput''',
         '''ContrastiveSearchDecoderOnlyOutput''',
     ]

try:
     if not is_tf_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCamelCase :				Dict						    =       [
         '''TFForcedBOSTokenLogitsProcessor''',
         '''TFForcedEOSTokenLogitsProcessor''',
         '''TFLogitsProcessor''',
         '''TFLogitsProcessorList''',
         '''TFLogitsWarper''',
         '''TFMinLengthLogitsProcessor''',
         '''TFNoBadWordsLogitsProcessor''',
         '''TFNoRepeatNGramLogitsProcessor''',
         '''TFRepetitionPenaltyLogitsProcessor''',
         '''TFTemperatureLogitsWarper''',
         '''TFTopKLogitsWarper''',
         '''TFTopPLogitsWarper''',
         '''TFForceTokensLogitsProcessor''',
         '''TFSuppressTokensAtBeginLogitsProcessor''',
         '''TFSuppressTokensLogitsProcessor''',
     ]
     UpperCamelCase :				List[Any]						    =       [
         '''TFGenerationMixin''',
         '''tf_top_k_top_p_filtering''',
         '''TFGreedySearchDecoderOnlyOutput''',
         '''TFGreedySearchEncoderDecoderOutput''',
         '''TFSampleEncoderDecoderOutput''',
         '''TFSampleDecoderOnlyOutput''',
         '''TFBeamSearchEncoderDecoderOutput''',
         '''TFBeamSearchDecoderOnlyOutput''',
         '''TFBeamSampleEncoderDecoderOutput''',
         '''TFBeamSampleDecoderOnlyOutput''',
         '''TFContrastiveSearchEncoderDecoderOutput''',
         '''TFContrastiveSearchDecoderOnlyOutput''',
     ]

try:
     if not is_flax_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCamelCase :				Tuple						    =       [
         '''FlaxForcedBOSTokenLogitsProcessor''',
         '''FlaxForcedEOSTokenLogitsProcessor''',
         '''FlaxLogitsProcessor''',
         '''FlaxLogitsProcessorList''',
         '''FlaxLogitsWarper''',
         '''FlaxMinLengthLogitsProcessor''',
         '''FlaxTemperatureLogitsWarper''',
         '''FlaxTopKLogitsWarper''',
         '''FlaxTopPLogitsWarper''',
     ]
     UpperCamelCase :				Any						    =       [
         '''FlaxGenerationMixin''',
         '''FlaxGreedySearchOutput''',
         '''FlaxSampleOutput''',
         '''FlaxBeamSearchOutput''',
     ]

if TYPE_CHECKING:
     from .configuration_utils import GenerationConfig
     from .streamers import TextIteratorStreamer, TextStreamer

     try:
          if not is_torch_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .beam_constraints import Constraint, ConstraintListState, DisjunctiveConstraint, PhrasalConstraint
          from .beam_search import BeamHypotheses, BeamScorer, BeamSearchScorer, ConstrainedBeamSearchScorer
          from .logits_process import (
              EncoderNoRepeatNGramLogitsProcessor,
              EncoderRepetitionPenaltyLogitsProcessor,
              EpsilonLogitsWarper,
              EtaLogitsWarper,
              ExponentialDecayLengthPenalty,
              ForcedBOSTokenLogitsProcessor,
              ForcedEOSTokenLogitsProcessor,
              HammingDiversityLogitsProcessor,
              InfNanRemoveLogitsProcessor,
              LogitNormalization,
              LogitsProcessor,
              LogitsProcessorList,
              LogitsWarper,
              MinLengthLogitsProcessor,
              MinNewTokensLengthLogitsProcessor,
              NoBadWordsLogitsProcessor,
              NoRepeatNGramLogitsProcessor,
              PrefixConstrainedLogitsProcessor,
              RepetitionPenaltyLogitsProcessor,
              SequenceBiasLogitsProcessor,
              TemperatureLogitsWarper,
              TopKLogitsWarper,
              TopPLogitsWarper,
              TypicalLogitsWarper,
          )
          from .stopping_criteria import (
              MaxLengthCriteria,
              MaxNewTokensCriteria,
              MaxTimeCriteria,
              StoppingCriteria,
              StoppingCriteriaList,
              validate_stopping_criteria,
          )
          from .utils import (
              BeamSampleDecoderOnlyOutput,
              BeamSampleEncoderDecoderOutput,
              BeamSearchDecoderOnlyOutput,
              BeamSearchEncoderDecoderOutput,
              ContrastiveSearchDecoderOnlyOutput,
              ContrastiveSearchEncoderDecoderOutput,
              GenerationMixin,
              GreedySearchDecoderOnlyOutput,
              GreedySearchEncoderDecoderOutput,
              SampleDecoderOnlyOutput,
              SampleEncoderDecoderOutput,
              top_k_top_p_filtering,
          )

     try:
          if not is_tf_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .tf_logits_process import (
              TFForcedBOSTokenLogitsProcessor,
              TFForcedEOSTokenLogitsProcessor,
              TFForceTokensLogitsProcessor,
              TFLogitsProcessor,
              TFLogitsProcessorList,
              TFLogitsWarper,
              TFMinLengthLogitsProcessor,
              TFNoBadWordsLogitsProcessor,
              TFNoRepeatNGramLogitsProcessor,
              TFRepetitionPenaltyLogitsProcessor,
              TFSuppressTokensAtBeginLogitsProcessor,
              TFSuppressTokensLogitsProcessor,
              TFTemperatureLogitsWarper,
              TFTopKLogitsWarper,
              TFTopPLogitsWarper,
          )
          from .tf_utils import (
              TFBeamSampleDecoderOnlyOutput,
              TFBeamSampleEncoderDecoderOutput,
              TFBeamSearchDecoderOnlyOutput,
              TFBeamSearchEncoderDecoderOutput,
              TFContrastiveSearchDecoderOnlyOutput,
              TFContrastiveSearchEncoderDecoderOutput,
              TFGenerationMixin,
              TFGreedySearchDecoderOnlyOutput,
              TFGreedySearchEncoderDecoderOutput,
              TFSampleDecoderOnlyOutput,
              TFSampleEncoderDecoderOutput,
              tf_top_k_top_p_filtering,
          )

     try:
          if not is_flax_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .flax_logits_process import (
              FlaxForcedBOSTokenLogitsProcessor,
              FlaxForcedEOSTokenLogitsProcessor,
              FlaxLogitsProcessor,
              FlaxLogitsProcessorList,
              FlaxLogitsWarper,
              FlaxMinLengthLogitsProcessor,
              FlaxTemperatureLogitsWarper,
              FlaxTopKLogitsWarper,
              FlaxTopPLogitsWarper,
          )
          from .flax_utils import FlaxBeamSearchOutput, FlaxGenerationMixin, FlaxGreedySearchOutput, FlaxSampleOutput
else:
     import sys

     UpperCamelCase :				List[Any]						    =       _LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)





def 							UpperCamelCase_  (				__snake_case			:						list[int]     )->      tuple[int, int]:




						'''simple docstring'''
						# base case
						if len(__snake_case     ) == 1:
												return a[0], a[0]
						else:
												# split A into half.
												__magic_name__ 		=			a[: len(__snake_case     ) // 2]
												__magic_name__ 		=			a[len(__snake_case     ) // 2 :]

												# 2 sub problems, 1/2 of original size.
												__magic_name__		,			__magic_name__ 		=			max_difference(__snake_case     )
												__magic_name__		,			__magic_name__ 		=			max_difference(__snake_case     )

												# get min of first and max of second
												# linear time
												__magic_name__ 		=			min(__snake_case     )
												__magic_name__ 		=			max(__snake_case     )

												# 3 cases, either (small1, big1),
												# (min_first, max_second), (small2, big2)
												# constant comparisons
												if biga - smalla > max_second - min_first and biga - smalla > biga - smalla:
																		return smalla, biga
												elif biga - smalla > max_second - min_first:
																		return smalla, biga
												else:
																		return min_first, max_second


if __name__ == "__main__":
					import doctest

					doctest.testmod()

