

import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput






@dataclass
class     __magic_name__     (							__lowerCAmelCase     ):
 UpperCAmelCase				     =    42
 UpperCAmelCase				     =    None
 UpperCAmelCase				     =    None






class     __magic_name__     (							unittest.TestCase     ):


 def _UpperCamelCase						(    self		:			Dict     )     ->   Optional[Any]:
   UpperCAmelCase          =	ModelOutputTest(a=3_0     )
   self.assertEqual(x.a      ,    3_0     )
   self.assertIsNone(x.b     )
   self.assertIsNone(x.c     )
   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x.d


 def _UpperCamelCase						(    self		:			Any     )     ->   str:
   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    b=1_0     )
   self.assertEqual(x[0]      ,    3_0     )
   self.assertEqual(x[1]      ,    1_0     )
   self.assertEqual(x[:2]      ,    (3_0, 1_0)     )
   self.assertEqual(x[:]      ,    (3_0, 1_0)     )

   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    c=1_0     )
   self.assertEqual(x[0]      ,    3_0     )
   self.assertEqual(x[1]      ,    1_0     )
   self.assertEqual(x[:2]      ,    (3_0, 1_0)     )
   self.assertEqual(x[:]      ,    (3_0, 1_0)     )


 def _UpperCamelCase						(    self		:			List[str]     )     ->   int:
   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    b=1_0     )
   self.assertEqual(x["a"]      ,    3_0     )
   self.assertEqual(x["b"]      ,    1_0     )
   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x["""c"""]

   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    c=1_0     )
   self.assertEqual(x["a"]      ,    3_0     )
   self.assertEqual(x["c"]      ,    1_0     )
   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x["""b"""]


 def _UpperCamelCase						(    self		:			Optional[Any]     )     ->   str:
   UpperCAmelCase          =	ModelOutputTest(a=3_0     )
   self.assertEqual(list(x.keys()     )      ,    ["a"]     )
   self.assertEqual(list(x.values()     )      ,    [3_0]     )
   self.assertEqual(list(x.items()     )      ,    [("a", 3_0)]     )
   self.assertEqual(list(_UpperCamelCase     )      ,    ["a"]     )

   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    b=1_0     )
   self.assertEqual(list(x.keys()     )      ,    ["a", "b"]     )
   self.assertEqual(list(x.values()     )      ,    [3_0, 1_0]     )
   self.assertEqual(list(x.items()     )      ,    [("a", 3_0), ("b", 1_0)]     )
   self.assertEqual(list(_UpperCamelCase     )      ,    ["a", "b"]     )

   UpperCAmelCase          =	ModelOutputTest(a=3_0      ,    c=1_0     )
   self.assertEqual(list(x.keys()     )      ,    ["a", "c"]     )
   self.assertEqual(list(x.values()     )      ,    [3_0, 1_0]     )
   self.assertEqual(list(x.items()     )      ,    [("a", 3_0), ("c", 1_0)]     )
   self.assertEqual(list(_UpperCamelCase     )      ,    ["a", "c"]     )

   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x.update({"d": 2_0}     )
   with self.assertRaises(_UpperCamelCase     ):
     del x["a"]
   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x.pop("a"     )
   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	x.setdefault("d"      ,    3_2     )


 def _UpperCamelCase						(    self		:			Tuple     )     ->   Dict:
   UpperCAmelCase          =	ModelOutputTest(a=3_0     )
   UpperCAmelCase          =	1_0
   self.assertEqual(x.a      ,    1_0     )
   self.assertEqual(x["a"]      ,    1_0     )


 def _UpperCamelCase						(    self		:			List[Any]     )     ->   List[Any]:
   UpperCAmelCase          =	ModelOutputTest(a=3_0     )
   UpperCAmelCase          =	1_0
   self.assertEqual(x.a      ,    1_0     )
   self.assertEqual(x["a"]      ,    1_0     )


 def _UpperCamelCase						(    self		:			Optional[int]     )     ->   List[str]:
   UpperCAmelCase          =	ModelOutputTest({"a": 3_0, "b": 1_0}     )
   self.assertEqual(list(x.keys()     )      ,    ["a", "b"]     )
   self.assertEqual(x.a      ,    3_0     )
   self.assertEqual(x.b      ,    1_0     )


 def _UpperCamelCase						(    self		:			Tuple     )     ->   Optional[int]:
   UpperCAmelCase          =	ModelOutputTest([("a", 3_0), ("b", 1_0)]     )
   self.assertEqual(list(x.keys()     )      ,    ["a", "b"]     )
   self.assertEqual(x.a      ,    3_0     )
   self.assertEqual(x.b      ,    1_0     )

   with self.assertRaises(_UpperCamelCase     ):
     UpperCAmelCase          =	ModelOutputTest([("a", 3_0), (1_0, 1_0)]     )

   UpperCAmelCase          =	ModelOutputTest(a=(3_0, 3_0)     )
   self.assertEqual(list(x.keys()     )      ,    ["a"]     )
   self.assertEqual(x.a      ,    (3_0, 3_0)     )




from __future__ import annotations







def     A__	(       __A ,			__A						):







    '''simple docstring'''
    _lowerCamelCase  :		List[str]			    =    [None] * (len(__A						) + len(__A						))

    _lowerCamelCase  :		Optional[int]			    =    0  # pointer to current index for left Half
    _lowerCamelCase  :		List[str]			    =    0  # pointer to current index for the right Half
    _lowerCamelCase  :		List[str]			    =    0  # pointer to current index for the sorted array Half

    while pointera < len(__A						) and pointera < len(__A						):
        if left_half[pointera] < right_half[pointera]:
            _lowerCamelCase  :		Optional[Any]			    =    left_half[pointera]
            pointera += 1
            index += 1
        else:
            _lowerCamelCase  :		List[Any]			    =    right_half[pointera]
            pointera += 1
            index += 1
    while pointera < len(__A						):
        _lowerCamelCase  :		int			    =    left_half[pointera]
        pointera += 1
        index += 1

    while pointera < len(__A						):
        _lowerCamelCase  :		Optional[Any]			    =    right_half[pointera]
        pointera += 1
        index += 1

    return sorted_array







def     A__	(       __A						):







    '''simple docstring'''
    if len(__A						) <= 1:
        return array
    # the actual formula to calculate the middle element = left + (right - left) // 2
    # this avoids integer overflow in case of large N
    _lowerCamelCase  :		int			    =    0 + (len(__A						) - 0) // 2

    # Split the array into halves till the array length becomes equal to One
    # merge the arrays of single length returned by mergeSort function and
    # pass them into the merge arrays function which merges the array
    _lowerCamelCase  :		List[str]			    =    array[:middle]
    _lowerCamelCase  :		Optional[int]			    =    array[middle:]

    return merge(merge_sort(__A						) ,			merge_sort(__A						)						)


if __name__ == "__main__":
    import doctest

    doctest.testmod()




