






"""simple docstring"""







lowerCAmelCase_	:    str            =      [0, 2, 4, 6, 8]
lowerCAmelCase_	:    Optional[Any]            =      [1, 3, 5, 7, 9]






def       _lowerCAmelCase       (      lowerCAmelCase	,      lowerCAmelCase	,      lowerCAmelCase	,      lowerCAmelCase		):







       '''simple docstring'''
       if remaining_length == 0:
              if digits[0] == 0 or digits[-1] == 0:
                     return 0

              for i in range(length // 2 - 1	,      -1	,      -1		):
                     remainder += digits[i] + digits[length - i - 1]

                     if remainder % 2 == 0:
                            return 0

                     remainder //= 10

              return 1

       if remaining_length == 1:
              if remainder % 2 == 0:
                     return 0

              UpperCAmelCase	    =			0
              for digit in range(10		):
                     UpperCAmelCase	    =			digit
                     result += reversible_numbers(
                         0	,      (remainder + 2 * digit) // 10	,      lowerCAmelCase	,      lowerCAmelCase		)
              return result

       UpperCAmelCase	    =			0
       for digita in range(10		):
              UpperCAmelCase	    =			digita

              if (remainder + digita) % 2 == 0:
                     UpperCAmelCase	    =			ODD_DIGITS
              else:
                     UpperCAmelCase	    =			EVEN_DIGITS

              for digita in other_parity_digits:
                     UpperCAmelCase	    =			digita
                     result += reversible_numbers(
                         remaining_length - 2	,      (remainder + digita + digita) // 10	,      lowerCAmelCase	,      lowerCAmelCase	,      )
       return result






def       _lowerCAmelCase       (      lowerCAmelCase = 9		):







       '''simple docstring'''
       UpperCAmelCase	    =			0
       for length in range(1	,      max_power + 1		):
              result += reversible_numbers(lowerCAmelCase	,      0	,      [0] * length	,      lowerCAmelCase		)
       return result


if __name__ == "__main__":
 print(F'{solution() = }')








"""simple docstring"""







def       _lowerCAmelCase       (      lowerCAmelCase		):







       '''simple docstring'''
       UpperCAmelCase	    =			0
       UpperCAmelCase	    =			len(lowerCAmelCase		)

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

       return num_inversions






def       _lowerCAmelCase       (      lowerCAmelCase		):







       '''simple docstring'''
       if len(lowerCAmelCase		) <= 1:
              return arr, 0
       UpperCAmelCase	    =			len(lowerCAmelCase		) // 2
       UpperCAmelCase	    =			arr[0:mid]
       UpperCAmelCase	    =			arr[mid:]

       UpperCAmelCase    ,       UpperCAmelCase	    =			count_inversions_recursive(lowerCAmelCase		)
       UpperCAmelCase    ,       UpperCAmelCase	    =			count_inversions_recursive(lowerCAmelCase		)
       UpperCAmelCase    ,       UpperCAmelCase	    =			_count_cross_inversions(lowerCAmelCase	,      lowerCAmelCase		)

       UpperCAmelCase	    =			inversion_p + inversions_q + cross_inversions
       return c, num_inversions






def       _lowerCAmelCase       (      lowerCAmelCase	,      lowerCAmelCase		):







       '''simple docstring'''
       UpperCAmelCase	    =			[]
       UpperCAmelCase	    =			UpperCAmelCase	    =			UpperCAmelCase	    =			0
       while i < len(lowerCAmelCase		) and j < len(lowerCAmelCase		):
              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(lowerCAmelCase		) - i
                     r.append(q[j]		)
                     j += 1
              else:
                     r.append(p[i]		)
                     i += 1

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

       return r, num_inversion






def       _lowerCAmelCase       (      ):







       '''simple docstring'''
       UpperCAmelCase	    =			[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)

       UpperCAmelCase	    =			count_inversions_bf(lowerCAmelCase		)
       UpperCAmelCase    ,       UpperCAmelCase	    =			count_inversions_recursive(lowerCAmelCase		)

       assert num_inversions_bf == num_inversions_recursive == 8

       print("""number of inversions = """	,      lowerCAmelCase		)

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

       arr_a.sort()
       UpperCAmelCase	    =			count_inversions_bf(lowerCAmelCase		)
       UpperCAmelCase    ,       UpperCAmelCase	    =			count_inversions_recursive(lowerCAmelCase		)

       assert num_inversions_bf == num_inversions_recursive == 0
       print("""number of inversions = """	,      lowerCAmelCase		)

       # an empty list should also have zero inversions
       UpperCAmelCase	    =			[]
       UpperCAmelCase	    =			count_inversions_bf(lowerCAmelCase		)
       UpperCAmelCase    ,       UpperCAmelCase	    =			count_inversions_recursive(lowerCAmelCase		)

       assert num_inversions_bf == num_inversions_recursive == 0
       print("""number of inversions = """	,      lowerCAmelCase		)


if __name__ == "__main__":
 main()
