"""
p82 — Gas Station (LC 134)

INVARIANT (skip lemma): If starting at s, tank first goes negative at i, then
  no j in [s, i] is a valid start. Reset start to i+1.

INVARIANT (global): A valid start exists iff sum(gas) >= sum(cost).
"""
from __future__ import annotations

import random
from typing import List


def can_complete_circuit(gas: List[int], cost: List[int]) -> int:
    """One-pass O(n) skip greedy. Returns starting index or -1."""
    total = 0
    tank = 0
    start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:
            # Skip past the failure point — every j in [start, i] also fails.
            start = i + 1
            tank = 0
    return start if total >= 0 else -1


def can_complete_circuit_prefix_min(gas: List[int], cost: List[int]) -> int:
    """O(n) via 'start right after the global minimum prefix sum' identity."""
    n = len(gas)
    total = 0
    min_prefix = 0
    min_idx = -1  # if min is never reached, start at 0
    for i in range(n):
        total += gas[i] - cost[i]
        if total < min_prefix:
            min_prefix = total
            min_idx = i
    return -1 if total < 0 else (min_idx + 1) % n


def can_complete_circuit_brute(gas: List[int], cost: List[int]) -> int:
    """Oracle: simulate every start. O(n^2)."""
    n = len(gas)
    for start in range(n):
        tank = 0
        ok = True
        for k in range(n):
            i = (start + k) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                ok = False
                break
        if ok:
            return start
    return -1


def _is_valid_start(gas: List[int], cost: List[int], start: int) -> bool:
    if start == -1:
        return sum(gas) < sum(cost)
    n = len(gas)
    tank = 0
    for k in range(n):
        i = (start + k) % n
        tank += gas[i] - cost[i]
        if tank < 0:
            return False
    return True


def edge_cases() -> None:
    # LC canonical example.
    assert can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3

    # Impossible.
    assert can_complete_circuit([2, 3, 4], [3, 4, 3]) == -1

    # Single station, gas == cost.
    assert can_complete_circuit([5], [5]) == 0

    # Single station, gas < cost.
    assert can_complete_circuit([1], [2]) == -1

    # All costs zero — start at 0.
    assert can_complete_circuit([1, 2, 3], [0, 0, 0]) == 0


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(1, 8)
        gas = [rng.randint(0, 5) for _ in range(n)]
        cost = [rng.randint(0, 5) for _ in range(n)]

        got = can_complete_circuit(gas[:], cost[:])
        got2 = can_complete_circuit_prefix_min(gas[:], cost[:])
        brute = can_complete_circuit_brute(gas[:], cost[:])

        # All three must either all return -1, or each return a valid start.
        feasible = sum(gas) >= sum(cost) and brute != -1
        if not feasible:
            assert got == -1 and got2 == -1 and brute == -1, (gas, cost, got, got2, brute)
        else:
            assert _is_valid_start(gas, cost, got), (gas, cost, got)
            assert _is_valid_start(gas, cost, got2), (gas, cost, got2)
            assert _is_valid_start(gas, cost, brute), (gas, cost, brute)


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