
'''simple docstring'''







_lowercase :  Dict    							=       [4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
_lowercase :  str    							=       [3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
_lowercase :  Dict    							=       {
    0: """Sunday""",
    1: """Monday""",
    2: """Tuesday""",
    3: """Wednesday""",
    4: """Thursday""",
    5: """Friday""",
    6: """Saturday""",
}
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: int      ,      __SCREAMING_SNAKE_CASE					: int      ,      __SCREAMING_SNAKE_CASE					: int							):



						"""simple docstring"""





						assert len(str(UpperCAmelCase_							)							) > 2, "year should be in YYYY format"
						assert 1 <= month <= 12, "month should be between 1 to 12"
						assert 1 <= day <= 31, "day should be between 1 to 31"

						# Doomsday algorithm:
						lowercase_	:     List[Any]													=       year // 100
						lowercase_	:     Dict													=       (5 * (century % 4) + 2) % 7
						lowercase_	:     Union[str, Any]													=       year % 100
						lowercase_	:     str													=       centurian % 12
						lowercase_	:     List[Any]													=       (
						    (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
						) % 7
						lowercase_	:     Union[str, Any]													=       (
						    DOOMSDAY_NOT_LEAP[month - 1]
						    if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
						    else DOOMSDAY_LEAP[month - 1]
						)
						lowercase_	:     Union[str, Any]													=       (dooms_day + day - day_anchor) % 7
						return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
							import doctest

							doctest.testmod()







'''simple docstring'''



def 			UpperCAmelCase__					(	UpperCAmelCase_    :				List[Any]							)     ->		str:
     __lowerCamelCase   :	Tuple								=		0
     __lowerCamelCase   :	Optional[int]								=		len(UpperCAmelCase_							)

     for i in range(n - 1							):
          for j in range(i + 1      ,    UpperCAmelCase_							):
               if arr[i] > arr[j]:
                    num_inversions += 1

     return num_inversions



def 			UpperCAmelCase__					(	UpperCAmelCase_    :				str							)     ->		Optional[int]:
     if len(UpperCAmelCase_							) <= 1:
          return arr, 0
     __lowerCamelCase   :	str								=		len(UpperCAmelCase_							) // 2
     __lowerCamelCase   :	List[Any]								=		arr[0:mid]
     __lowerCamelCase   :	List[str]								=		arr[mid:]

     __lowerCamelCase				,       __lowerCamelCase   :	int								=		count_inversions_recursive(UpperCAmelCase_							)
     __lowerCamelCase				,       __lowerCamelCase   :	Optional[Any]								=		count_inversions_recursive(UpperCAmelCase_							)
     __lowerCamelCase				,       __lowerCamelCase   :	Any								=		_count_cross_inversions(UpperCAmelCase_      ,    UpperCAmelCase_							)

     __lowerCamelCase   :	Optional[int]								=		inversion_p + inversions_q + cross_inversions
     return c, num_inversions



def 			UpperCAmelCase__					(	UpperCAmelCase_    :				List[Any]      ,    UpperCAmelCase_    :				List[str]							)     ->		Optional[Any]:
     __lowerCamelCase   :	List[str]								=		[]
     __lowerCamelCase   :	Optional[int]								=		0
     while i < len(UpperCAmelCase_							) and j < len(UpperCAmelCase_							):
          if p[i] > q[j]:
               # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
               # These are all inversions. The claim emerges from the
               # property that P is sorted.
               num_inversion += len(UpperCAmelCase_							) - i
               r.append(q[j]							)
               j += 1
          else:
               r.append(p[i]							)
               i += 1

     if i < len(UpperCAmelCase_							):
          r.extend(p[i:]							)
     else:
          r.extend(q[j:]							)

     return r, num_inversion



def 			UpperCAmelCase__					(	)     ->		List[str]:
     __lowerCamelCase   :	Any								=		[10, 2, 1, 5, 5, 2, 11]

     # this arr has 8 inversions:
     # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

     __lowerCamelCase   :	Optional[Any]								=		count_inversions_bf(UpperCAmelCase_							)
     __lowerCamelCase				,       __lowerCamelCase   :	Dict								=		count_inversions_recursive(UpperCAmelCase_							)

     assert num_inversions_bf == num_inversions_recursive == 8

     print('number of inversions = '      ,    UpperCAmelCase_							)

     # testing an array with zero inversion (a sorted arr_1)

     arr_a.sort()
     __lowerCamelCase   :	Optional[Any]								=		count_inversions_bf(UpperCAmelCase_							)
     __lowerCamelCase				,       __lowerCamelCase   :	int								=		count_inversions_recursive(UpperCAmelCase_							)

     assert num_inversions_bf == num_inversions_recursive == 0
     print('number of inversions = '      ,    UpperCAmelCase_							)

     # an empty list should also have zero inversions
     __lowerCamelCase   :	Dict								=		[]
     __lowerCamelCase   :	Optional[Any]								=		count_inversions_bf(UpperCAmelCase_							)
     __lowerCamelCase				,       __lowerCamelCase   :	Union[str, Any]								=		count_inversions_recursive(UpperCAmelCase_							)

     assert num_inversions_bf == num_inversions_recursive == 0
     print('number of inversions = '      ,    UpperCAmelCase_							)


if __name__ == "__main__":
      main()






