"""Kapalı aralıklar [baş, son] üzerinde işlemler."""
from typing import List, Tuple

Interval = Tuple[int, int]


def validate(iv: Interval) -> None:
    if len(iv) != 2:
        raise ValueError("aralık iki elemanlı olmalı")
    if iv[0] > iv[1]:
        raise ValueError(f"geçersiz aralık: {iv}")


def merge(intervals: List[Interval]) -> List[Interval]:
    """Çakışan veya bitişik (ör. [1,3] ve [4,5]) aralıkları birleştirir."""
    for iv in intervals:
        validate(iv)
    result: List[Interval] = []
    for start, end in sorted(intervals):
        if result and start <= result[-1][1] + 1:
            result[-1] = (result[-1][0], max(result[-1][1], end))
        else:
            result.append((start, end))
    return result


def total_length(intervals: List[Interval]) -> int:
    """Birleştirilmiş aralıkların kapsadığı tam sayı adedi."""
    return sum(end - start + 1 for start, end in merge(intervals))


def contains(intervals: List[Interval], x: int) -> bool:
    lo, hi = 0, len(merged := merge(intervals)) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        s, e = merged[mid]
        if x < s:
            hi = mid - 1
        elif x > e:
            lo = mid + 1
        else:
            return True
    return False


def gaps(intervals: List[Interval], lower: int, upper: int) -> List[Interval]:
    """[lower, upper] içinde hiçbir aralığın kapsamadığı boşluklar."""
    if lower > upper:
        raise ValueError("lower > upper")
    out: List[Interval] = []
    cur = lower
    for s, e in merge(intervals):
        if e < lower or s > upper:
            continue
        if s > cur:
            out.append((cur, s - 1))
        cur = max(cur, e + 1)
    if cur <= upper:
        out.append((cur, upper))
    return out