




from typing import List

from packaging import version
from sklearn.metrics import fa_score

import datasets
from datasets.config import PY_VERSION


if PY_VERSION < version.parse('3.8'):
   import importlib_metadata
else:
   import importlib.metadata as importlib_metadata


# TODO(Patrick/Anton)
UpperCAmelCase__    :							Tuple       		=     '\\n'

UpperCAmelCase__    :							List[str]       		=     '\\n    XTREME-S is a benchmark to evaluate universal cross-lingual speech representations in many languages.\n    XTREME-S covers four task families: speech recognition, classification, speech-to-text translation and retrieval.\n'

UpperCAmelCase__    :							List[Any]       		=     '\nCompute XTREME-S evaluation metric associated to each XTREME-S dataset.\nArgs:\n    predictions: list of predictions to score.\n        Each translation should be tokenized into a list of tokens.\n    references: list of lists of references for each translation.\n        Each reference should be tokenized into a list of tokens.\n    bleu_kwargs: optional dict of keywords to be passed when computing \'bleu\'.\n        Keywords include Dict can be one of \'smooth_method\', \'smooth_value\', \'force\', \'lowercase\',\n        \'tokenize\', \'use_effective_order\'.\n    wer_kwargs: optional dict of keywords to be passed when computing \'wer\' and \'cer\'.\n        Keywords include \'concatenate_texts\'.\nReturns: depending on the XTREME-S task, one or several of:\n    "accuracy": Accuracy - for \'fleurs-lang_id\', \'minds14\'\n    "f1": F1 score - for \'minds14\'\n    "wer": Word error rate - for \'mls\', \'fleurs-asr\', \'voxpopuli\', \'babel\'\n    "cer": Character error rate - for \'mls\', \'fleurs-asr\', \'voxpopuli\', \'babel\'\n    "bleu": BLEU score according to the `sacrebleu` metric - for \'covost2\'\nExamples:\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'mls\')  # \'mls\', \'voxpopuli\', \'fleurs-asr\' or \'babel\'\n    >>> references = ["it is sunny here", "paper and pen are essentials"]\n    >>> predictions = ["it\'s sunny", "paper pen are essential"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'wer\': 0.56, \'cer\': 0.27}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'covost2\')\n    >>> references = ["bonjour paris", "il est necessaire de faire du sport de temps en temp"]\n    >>> predictions = ["bonjour paris", "il est important de faire du sport souvent"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'bleu\': 31.65}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'fleurs-lang_id\')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'accuracy\': 0.6}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'minds14\')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'f1\': 0.58, \'accuracy\': 0.6}\n'

UpperCAmelCase__    :							int       		=     ['fleurs-asr', 'mls', 'voxpopuli', 'babel', 'covost2', 'fleurs-lang_id', 'minds14']
UpperCAmelCase__    :							Optional[int]       		=     ''

try:
   from jiwer import transforms as tr

   UpperCAmelCase__    :							Dict       		=     True
except ImportError:
   UpperCAmelCase__    :							Dict       		=     False

if _jiwer_available and version.parse(importlib_metadata.version('jiwer')) < version.parse('2.3.0'):

   class   UpperCAmelCase    (      tr.AbstractTransform ):






      def __init__(						self :							List[Any]    ,       UpperCamelCase_ :							str = " "  )->      str:
        _lowercase:			Tuple      =     sentence_delimiter






      def 			_a    (						self :							List[Any]    ,       UpperCamelCase_ :							str  )->      str:
        return list(UpperCamelCase_  )






      def 			_a    (						self :							Optional[int]    ,       UpperCamelCase_ :							List[str]  )->      Tuple:
        _lowercase:			Optional[Any]      =     []
        for sent_idx, sentence in enumerate(UpperCamelCase_  ):
          chars.extend(self.process_string(UpperCamelCase_  )  )
          if self.sentence_delimiter is not None and self.sentence_delimiter != "" and sent_idx < len(UpperCamelCase_  ) - 1:
            chars.append(self.sentence_delimiter  )
        return chars
   UpperCAmelCase__    :							Dict       		=     tr.Compose(
       [tr.RemoveMultipleSpaces(), tr.Strip(), SentencesToListOfCharacters(SENTENCE_DELIMITER)]
   )
elif _jiwer_available:
   UpperCAmelCase__    :							Tuple       		=     tr.Compose(
       [
           tr.RemoveMultipleSpaces(),
           tr.Strip(),
           tr.ReduceToSingleSentence(SENTENCE_DELIMITER),
           tr.ReduceToListOfListOfChars(),
       ]
   )
else:
   UpperCAmelCase__    :							Union[str, Any]       		=     None


def 		_lowerCamelCase					(       UpperCamelCase       ,  UpperCamelCase				)      ->		str:





  """simple docstring"""





  return float((preds == labels).mean()				)


def 		_lowerCamelCase					(       UpperCamelCase       ,  UpperCamelCase				)      ->		Tuple:





  """simple docstring"""





  return {
      "f1": float(fa_score(y_true=UpperCamelCase       ,  y_pred=UpperCamelCase       ,  average='macro'				)				),
      "accuracy": simple_accuracy(UpperCamelCase       ,  UpperCamelCase				),
  }


def 		_lowerCamelCase					(       UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase="exp"       ,  UpperCamelCase=None       ,  UpperCamelCase=False       ,  UpperCamelCase=False       ,  UpperCamelCase=None       ,  UpperCamelCase=False       ,  )      ->		Any:





  """simple docstring"""





  _lowercase:			str      =     [[label] for label in labels]
  _lowercase:			Optional[int]      =     list(UpperCamelCase				)
  try:
    import sacrebleu as scb
  except ImportError:
    raise ValueError(
        'sacrebleu has to be installed in order to apply the bleu metric for covost2.'
        'You can install it via `pip install sacrebleu`.'				)

  if version.parse(scb.__version__				) < version.parse('1.4.12'				):
    raise ImportWarning(
        'To use `sacrebleu`, the module `sacrebleu>=1.4.12` is required, and the current version of `sacrebleu` doesn\'t match this condition.\n'
        'You can install it with `pip install "sacrebleu>=1.4.12"`.'				)

  _lowercase:			Tuple      =     len(labels[0]				)
  if any(len(UpperCamelCase				) != references_per_prediction for refs in labels				):
    raise ValueError('Sacrebleu requires the same number of references for each prediction'				)
  _lowercase:			List[Any]      =     [[refs[i] for refs in labels] for i in range(UpperCamelCase				)]
  _lowercase:			Dict      =     scb.corpus_bleu(
      UpperCamelCase       ,  UpperCamelCase       ,  smooth_method=UpperCamelCase       ,  smooth_value=UpperCamelCase       ,  force=UpperCamelCase       ,  lowercase=UpperCamelCase       ,  use_effective_order=UpperCamelCase       ,  **({'tokenize': tokenize} if tokenize else {})       ,  )
  return {"bleu": output.score}


def 		_lowerCamelCase					(       UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase				)      ->		str:





  """simple docstring"""





  try:
    from jiwer import compute_measures
  except ImportError:
    raise ValueError(
        F'jiwer has to be installed in order to apply the wer metric for {config_name}.'
        'You can install it via `pip install jiwer`.'				)

  if concatenate_texts:
    _lowercase:			Any      =     compute_measures(UpperCamelCase       ,  UpperCamelCase				)['wer']

    _lowercase:			str      =     compute_measures(UpperCamelCase       ,  UpperCamelCase       ,  truth_transform=UpperCamelCase       ,  hypothesis_transform=UpperCamelCase				)['wer']
    return {"wer": wer, "cer": cer}
  else:

    def compute_score(UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase="wer"				):
      _lowercase:			List[str]      =     0
      _lowercase:			Any      =     0
      for prediction, reference in zip(UpperCamelCase       ,  UpperCamelCase				):
        if score_type == "wer":
          _lowercase:			int      =     compute_measures(UpperCamelCase       ,  UpperCamelCase				)
        elif score_type == "cer":
          _lowercase:			Dict      =     compute_measures(
              UpperCamelCase       ,  UpperCamelCase       ,  truth_transform=UpperCamelCase       ,  hypothesis_transform=UpperCamelCase				)
        incorrect += measures["substitutions"] + measures["deletions"] + measures["insertions"]
        total += measures["substitutions"] + measures["deletions"] + measures["hits"]
      return incorrect / total

    return {"wer": compute_score(UpperCamelCase       ,  UpperCamelCase       ,  'wer'				), "cer": compute_score(UpperCamelCase       ,  UpperCamelCase       ,  'cer'				)}





@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION ,       _KWARGS_DESCRIPTION )
class   UpperCAmelCase    (      datasets.Metric ):






   def 			_a    (						self :							str  )->      List[Any]:
     if self.config_name not in _CONFIG_NAMES:
       raise KeyError(f'You should supply a configuration name selected in {_CONFIG_NAMES}'  )

     _lowercase:			Tuple      =     'int64' if self.config_name in ['fleurs-lang_id', 'minds14'] else 'string'

     return datasets.MetricInfo(
         description=_DESCRIPTION    ,       citation=_CITATION    ,       inputs_description=_KWARGS_DESCRIPTION    ,       features=datasets.Features(
             {'predictions': datasets.Value(UpperCamelCase_  ), 'references': datasets.Value(UpperCamelCase_  )}  )    ,       codebase_urls=[]    ,       reference_urls=[]    ,       format='numpy'    ,       )






   def 			_a    (						self :							int    ,       UpperCamelCase_ :							Any    ,       UpperCamelCase_ :							List[Any]    ,       UpperCamelCase_ :							List[Any]=None    ,       UpperCamelCase_ :							Tuple=None  )->      Dict:
     _lowercase:			int      =     bleu_kwargs if bleu_kwargs is not None else {}
     _lowercase:			Optional[Any]      =     wer_kwargs if wer_kwargs is not None else {}

     if self.config_name == "fleurs-lang_id":
       return {"accuracy": simple_accuracy(UpperCamelCase_    ,       UpperCamelCase_  )}
     elif self.config_name == "minds14":
       return fa_and_simple_accuracy(UpperCamelCase_    ,       UpperCamelCase_  )
     elif self.config_name == "covost2":
       _lowercase:			Union[str, Any]      =     bleu_kwargs.pop('smooth_method'    ,       'exp'  )
       _lowercase:			Optional[Any]      =     bleu_kwargs.pop('smooth_value'    ,       UpperCamelCase_  )
       _lowercase:			int      =     bleu_kwargs.pop('force'    ,       UpperCamelCase_  )
       _lowercase:			Dict      =     bleu_kwargs.pop('lowercase'    ,       UpperCamelCase_  )
       _lowercase:			Any      =     bleu_kwargs.pop('tokenize'    ,       UpperCamelCase_  )
       _lowercase:			int      =     bleu_kwargs.pop('use_effective_order'    ,       UpperCamelCase_  )
       return bleu(
           preds=UpperCamelCase_    ,       labels=UpperCamelCase_    ,       smooth_method=UpperCamelCase_    ,       smooth_value=UpperCamelCase_    ,       force=UpperCamelCase_    ,       lowercase=UpperCamelCase_    ,       tokenize=UpperCamelCase_    ,       use_effective_order=UpperCamelCase_    ,       )
     elif self.config_name in ["fleurs-asr", "mls", "voxpopuli", "babel"]:
       _lowercase:			List[str]      =     wer_kwargs.pop('concatenate_texts'    ,       UpperCamelCase_  )
       return wer_and_cer(UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_    ,       self.config_name  )
     else:
       raise KeyError(f'You should supply a configuration name selected in {_CONFIG_NAMES}'  )






from __future__ import annotations

class   UpperCAmelCase    :






   def __init__(						self :							List[Any]    ,       UpperCamelCase_ :							int  )->      None:
     _lowercase:			Optional[Any]      =     data
     _lowercase:			Optional[int]      =     None

class   UpperCAmelCase    :






   def __init__(						self :							Optional[Any]  )->      Union[str, Any]:
     _lowercase:			List[str]      =     None






   def 			_a    (						self :							List[Any]    ,       UpperCamelCase_ :							int  )->      int:
     _lowercase:			Any      =     Node(UpperCamelCase_  )
     _lowercase:			List[Any]      =     self.head
     _lowercase:			List[str]      =     new_node
     return self.head.data






   def 			_a    (						self :							Tuple  )->      int | None:
     _lowercase:			List[str]      =     self.head
     _lowercase:			str      =     self.head
     if self.head:
       while fast_pointer and fast_pointer.next:
         _lowercase:			Optional[int]      =     fast_pointer.next.next
         _lowercase:			Tuple      =     slow_pointer.next
       return slow_pointer.data
     else:
       print('No element found.'  )
       return None


if __name__ == "__main__":
   UpperCAmelCase__    :							Union[str, Any]       		=     LinkedList()
   for _ in range(int(input().strip())):
      UpperCAmelCase__    :							List[Any]       		=     int(input().strip())
      link.push(data)
   print(link.middle_element())
