"""
p81 — Queue Reconstruction by Height (LC 406)

INVARIANT: Sort by (-h, k). Iterate; insert(k, person).
  When inserting person p=(h,k), all already-placed persons have height >= h,
  so the count of taller-or-equal in front == insertion index. Hence k == index.

Sibling: LC 354 Russian Doll Envelopes (sort (w asc, h desc) → LIS on h).
"""
from __future__ import annotations

import random
from itertools import permutations
from typing import List, Tuple


def reconstruct_queue(people: List[List[int]]) -> List[List[int]]:
    """Optimal: sort tall-first, ties by ascending k, then insert at k. O(n^2)."""
    # Sort by height descending; tie-break by k ascending.
    people_sorted = sorted(people, key=lambda p: (-p[0], p[1]))
    result: List[List[int]] = []
    for h, k in people_sorted:
        # INVARIANT: every element in result has height >= h,
        # so inserting at index k makes exactly k taller-or-equal people in front.
        result.insert(k, [h, k])
    return result


def reconstruct_queue_brute(people: List[List[int]]) -> List[List[int]]:
    """Oracle: try all n! permutations; return first that satisfies all k counts."""
    n = len(people)
    for perm in permutations(range(n)):
        arrangement = [people[i] for i in perm]
        ok = True
        for i, (h, k) in enumerate(arrangement):
            # count strictly-before with height >= h
            cnt = sum(1 for j in range(i) if arrangement[j][0] >= h)
            if cnt != k:
                ok = False
                break
        if ok:
            return arrangement
    return []


def _is_valid(arrangement: List[List[int]]) -> bool:
    for i, (h, k) in enumerate(arrangement):
        cnt = sum(1 for j in range(i) if arrangement[j][0] >= h)
        if cnt != k:
            return False
    return True


def edge_cases() -> None:
    # Standard LC example.
    out = reconstruct_queue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]])
    assert out == [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]], out

    # Single person.
    assert reconstruct_queue([[5, 0]]) == [[5, 0]]

    # All same height, k = 0..n-1.
    out = reconstruct_queue([[3, 0], [3, 1], [3, 2], [3, 3]])
    assert _is_valid(out), out

    # Strictly increasing heights, all k=0 → reverse by height descending? No: k=0 means each is at index 0 of taller-or-equal, so the tallest is at front, then next tallest, etc.
    out = reconstruct_queue([[1, 0], [2, 0], [3, 0]])
    assert _is_valid(out), out


def _gen_valid_people(rng: random.Random, n: int) -> List[List[int]]:
    """Generate a valid (h, k) list by constructing a random queue and computing k for each."""
    heights = [rng.randint(1, 5) for _ in range(n)]
    rng.shuffle(heights)
    people: List[List[int]] = []
    for i, h in enumerate(heights):
        k = sum(1 for j in range(i) if heights[j] >= h)
        people.append([h, k])
    rng.shuffle(people)  # scramble input order
    return people


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(1, 6)
        people = _gen_valid_people(rng, n)

        got = reconstruct_queue([p[:] for p in people])
        # Validate (not equal to brute — multiple valid arrangements possible).
        assert _is_valid(got), (people, got)

        # Also brute should find some valid (not necessarily ours).
        brute = reconstruct_queue_brute([p[:] for p in people])
        assert _is_valid(brute), (people, brute)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")