Majority-Element-D&C

from typing import List

def majority(A: List[int], l: int, r: int):
    if l == r:
        return A[l]
    mid = (l + r) // 2
    a = majority(A, mid + 1, r)
    b = majority(A, l, mid)
    if a == b:
        return a
    count_a = 0
    count_b = 0
    for i in range(l, r + 1):
        if A[i] == a:
            count_a += 1
        elif A[i] == b:
            count_b += 1
    if count_a > (r - l + 1) / 2:
        return a
    elif count_b > (r - l + 1) / 2:
        return b
    else:
        return -1 # not found