



"""simple docstring"""





def   a__      ( lowerCAmelCase__ ):
      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   a__      ( lowerCAmelCase__ ):
      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   a__      ( lowerCAmelCase__      ,     lowerCAmelCase__ ):
      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   a__      ( ):
      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()











"""simple docstring"""





# Copyright 2023 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


__A											=						{
    """configuration_mgp_str""": ["""MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP""", """MgpstrConfig"""],
    """processing_mgp_str""": ["""MgpstrProcessor"""],
    """tokenization_mgp_str""": ["""MgpstrTokenizer"""],
}

try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  __A											=						[
      """MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST""",
      """MgpstrModel""",
      """MgpstrPreTrainedModel""",
      """MgpstrForSceneTextRecognition""",
  ]

if TYPE_CHECKING:
  from .configuration_mgp_str import MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP, MgpstrConfig
  from .processing_mgp_str import MgpstrProcessor
  from .tokenization_mgp_str import MgpstrTokenizer

  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_mgp_str import (
        MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST,
        MgpstrForSceneTextRecognition,
        MgpstrModel,
        MgpstrPreTrainedModel,
    )
else:
  import sys

  __A											=						_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)
