"""BTVN: đếm, tìm biên và phần tử cố định (A[i]=i).

Python3:
  python3 g11-cs-thuc-hanh-tim-kiem.py dem "-2 1 1 1 4 7" 1
  python3 g11-cs-thuc-hanh-tim-kiem.py bat-ky "4 1 4 0 4" 4
  python3 g11-cs-thuc-hanh-tim-kiem.py co-dinh "-2 0 2 5 9" --kieu tang
  python3 g11-cs-thuc-hanh-tim-kiem.py co-dinh "0 0 0" --kieu khong-giam
  python3 g11-cs-thuc-hanh-tim-kiem.py co-dinh "1 0" --kieu bat-ky
Không sắp xếp lại dãy khi tìm phần tử cố định của dữ liệu gốc.
"""
import argparse


def count_linear(A, C):
    count = 0
    for value in A:
        if value == C:
            count += 1
    return count


def countNum(A, left, right, C):
    # A không giảm; tìm một vị trí rồi quét vùng trùng.
    if left > right:
        return 0
    mid = (left + right) // 2
    if A[mid] == C:
        start, end = mid, mid
        while start >= left and A[start] == C:
            start -= 1
        while end <= right and A[end] == C:
            end += 1
        return end - start - 1
    if A[mid] < C:
        return countNum(A, mid + 1, right, C)
    return countNum(A, left, mid - 1, C)


def count_region(A, left, right, C):
    if left > right:
        return None, None, 0
    mid = (left + right) // 2
    if A[mid] == C:
        start, end = mid, mid
        while start >= left and A[start] == C:
            start -= 1
        while end <= right and A[end] == C:
            end += 1
        return start + 1, end - 1, end - start - 1
    if A[mid] < C:
        return count_region(A, mid + 1, right, C)
    return count_region(A, left, mid - 1, C)


def count_any(A, left, right, K):
    if left > right:
        return 0
    mid = (left + right) // 2
    count = 1 if A[mid] == K else 0
    return (count + count_any(A, left, mid - 1, K)
            + count_any(A, mid + 1, right, K))


def fixvalue(A, left, right):
    # Chỉ dùng cho dãy SỐ NGUYÊN tăng thực sự.
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == mid:
        return mid
    if A[mid] < mid:
        return fixvalue(A, mid + 1, right)
    return fixvalue(A, left, mid - 1)


def findFix(A, left, right):
    # Bản tổng quát cho dãy số nguyên bất kì.
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == mid:
        return mid
    index = findFix(A, mid + 1, right)
    if index >= 0:
        return index
    return findFix(A, left, mid - 1)


def findFixPoint(A, left, right):
    # Dãy số nguyên không giảm; kiểm biên trước khi gọi bản tổng quát.
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == mid:
        return mid
    if mid + 1 <= A[right]:
        index = findFix(A, mid + 1, right)
        if index >= 0:
            return index
    if mid - 1 >= A[left]:
        index = findFix(A, left, mid - 1)
        if index >= 0:
            return index
    return -1


def firstInd(A, left, right, C):
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == C:
        earlier = firstInd(A, left, mid - 1, C)
        return earlier if earlier >= 0 else mid
    if A[mid] < C:
        return firstInd(A, mid + 1, right, C)
    return firstInd(A, left, mid - 1, C)


def lastInd(A, left, right, C):
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == C:
        later = lastInd(A, mid + 1, right, C)
        return later if later >= 0 else mid
    if A[mid] < C:
        return lastInd(A, mid + 1, right, C)
    return lastInd(A, left, mid - 1, C)


def count_bounds(A, C):
    first = firstInd(A, 0, len(A) - 1, C)
    if first < 0:
        return 0
    last = lastInd(A, 0, len(A) - 1, C)
    return last - first + 1


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_subparsers(dest='mode', required=True)
    for mode in ['dem', 'bat-ky']:
        sub = modes.add_parser(mode)
        sub.add_argument('array')
        sub.add_argument('C', type=int)
    fixed = modes.add_parser('co-dinh')
    fixed.add_argument('array')
    fixed.add_argument('--kieu', choices=['tang', 'khong-giam', 'bat-ky'], default='bat-ky')
    args = parser.parse_args()
    try:
        A = [int(x) for x in args.array.split()]
        ordered = all(A[i] <= A[i + 1] for i in range(len(A) - 1))
        if args.mode == 'dem':
            if not ordered:
                raise ValueError('Dãy cần sắp xếp không giảm.')
            print('Đếm tuần tự:', count_linear(A, args.C))
            print('Tìm rồi quét:', countNum(A, 0, len(A) - 1, args.C))
            print('Vùng và số lượng:', count_region(A, 0, len(A) - 1, args.C))
            print('Đếm bằng hai biên:', count_bounds(A, args.C))
        elif args.mode == 'bat-ky':
            print('Đếm tuần tự:', count_linear(A, args.C))
            print('Chia và đếm hai phía:', count_any(A, 0, len(A) - 1, args.C))
        else:
            if args.kieu == 'tang':
                if not all(A[i] < A[i + 1] for i in range(len(A) - 1)):
                    raise ValueError('Bản này cần dãy số nguyên tăng thực sự.')
                index = fixvalue(A, 0, len(A) - 1)
            elif args.kieu == 'khong-giam':
                if not ordered:
                    raise ValueError('Bản này cần dãy số nguyên không giảm.')
                index = findFixPoint(A, 0, len(A) - 1)
            else:
                index = findFix(A, 0, len(A) - 1)
            print('Chỉ số cố định:', index)
            if index >= 0:
                print('Giá trị:', A[index])
    except ValueError as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()