"""BTVN, Python3: nghịch đảo, mốt và tổng con liên tục lớn nhất.

python3 g11-cs-thuc-hanh-chia-de-tri.py dem "6 2 6 1"
python3 g11-cs-thuc-hanh-chia-de-tri.py liet-ke "6 2 6 1"
python3 g11-cs-thuc-hanh-chia-de-tri.py mot "-1 2 2 2 5 5"
python3 g11-cs-thuc-hanh-chia-de-tri.py tong "-4 5 -2 4 -6"
Các chỉ số tính từ0; các hàm bọc giữ dữ liệu gốc.
"""
import argparse


def count_simple(A):
    count = 0
    for i in range(len(A) - 1):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                count += 1
    return count


def merge_count(A, left, mid, right, temp):
    i, j, k = left, mid + 1, left
    count = 0
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            temp[k] = A[i]
            i += 1
        else:
            temp[k] = A[j]
            count += mid - i + 1
            j += 1
        k += 1
    while i <= mid:
        temp[k] = A[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = A[j]
        j += 1
        k += 1
    for k in range(left, right + 1):
        A[k] = temp[k]
    return count


def getInvCount(A, left, right, temp):
    if left >= right:
        return 0
    mid = (left + right) // 2
    countL = getInvCount(A, left, mid, temp)
    countR = getInvCount(A, mid + 1, right, temp)
    countM = merge_count(A, left, mid, right, temp)
    return countL + countR + countM


def count_fast(A):
    B = A.copy()
    temp = [0] * len(B)
    return getInvCount(B, 0, len(B) - 1, temp)


def pair_merge(B, C):
    # Mỗi bản ghi là (giá trị, chỉ số gốc), hai dãy đã sắp theo giá trị.
    result, pairs = [], []
    i = j = 0
    while i < len(B) and j < len(C):
        if B[i][0] <= C[j][0]:
            result.append(B[i])
            i += 1
        else:
            result.append(C[j])
            pairs.extend((B[t][1], C[j][1]) for t in range(i, len(B)))
            j += 1
    result.extend(B[i:])
    result.extend(C[j:])
    return result, pairs


def pair_sort(records):
    if len(records) <= 1:
        return records, []
    mid = len(records) // 2
    B, pairsL = pair_sort(records[:mid])
    C, pairsR = pair_sort(records[mid:])
    merged, pairsM = pair_merge(B, C)
    return merged, pairsL + pairsM + pairsR


def inversion_indices(A):
    records = [(value, i) for i, value in enumerate(A)]
    _, pairs = pair_sort(records)
    return pairs


def mode(A, left, right):
    if left > right:
        return None, 0
    mid = (left + right) // 2
    i = j = mid
    while i > left and A[i] == A[i - 1]:
        i -= 1
    while j < right and A[j] == A[j + 1]:
        j += 1
    m0, k0 = A[mid], j - i + 1
    m1, k1 = mode(A, left, mid - 1)
    m2, k2 = mode(A, mid + 1, right)
    if k0 >= k1 and k0 >= k2:
        return m0, k0
    if k1 >= k0 and k1 >= k2:
        return m1, k1
    return m2, k2


def maxSubarray(A, left, right):
    if left > right:
        return None, None, float('-inf')
    if left == right:
        return left, right, A[left]
    mid = (left + right) // 2
    sumL, maxL, total = A[mid], mid, 0
    for i in range(mid, left - 1, -1):
        total += A[i]
        if total > sumL:
            sumL, maxL = total, i
    sumR, maxR, total = A[mid + 1], mid + 1, 0
    for j in range(mid + 1, right + 1):
        total += A[j]
        if total > sumR:
            sumR, maxR = total, j
    sumX = sumL + sumR
    leftL, rightL, bestL = maxSubarray(A, left, mid)
    leftR, rightR, bestR = maxSubarray(A, mid + 1, right)
    if bestL >= bestR and bestL >= sumX:
        return leftL, rightL, bestL
    if bestR >= bestL and bestR >= sumX:
        return leftR, rightR, bestR
    return maxL, maxR, sumX


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('mode', choices=['dem', 'liet-ke', 'mot', 'tong'])
    parser.add_argument('array')
    args = parser.parse_args()
    try:
        A = [int(x) for x in args.array.split()]
        if args.mode == 'dem':
            print('Duyệt từng cặp:', count_simple(A))
            print('Chia để trị:', count_fast(A))
        elif args.mode == 'liet-ke':
            pairs = inversion_indices(A)
            print('Số cặp:', len(pairs))
            print('Cặp chỉ số gốc:', pairs)
            print('Cặp giá trị:', [(A[i], A[j]) for i, j in pairs])
        elif args.mode == 'mot':
            if any(A[i] > A[i + 1] for i in range(len(A) - 1)):
                raise ValueError('Bản tìm mốt cần dãy không giảm.')
            value, frequency = mode(A, 0, len(A) - 1)
            print('Mốt:', value)
            print('Số lần xuất hiện:', frequency)
        else:
            left, right, total = maxSubarray(A, 0, len(A) - 1)
            if left is None:
                print('Dãy rỗng: không có dãy con không rỗng.')
            else:
                print('Chỉ số đầu/cuối:', (left, right))
                print('Tổng lớn nhất:', total)
                print('Dãy con:', A[left:right + 1])
    except ValueError as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()