"""
p53 — Next Greater Element II (LeetCode 503, MEDIUM).

CIRCULAR array. For each index i, return the next STRICTLY greater value going
clockwise (wrapping around), or -1 if none anywhere in the array.

Implementations:
    next_greater_elements_doubled — iterate 2n, push only first pass. O(n).
    next_greater_elements_concat  — nums + nums, p52 logic, slice. O(n), 2x memory.
    next_greater_elements_brute   — O(n^2) scan-around-the-ring oracle.
"""
from __future__ import annotations
import random
from typing import List


def next_greater_elements_doubled(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [-1] * n
    # INVARIANT: stack holds INDICES (0..n-1); nums-values at those indices are
    # STRICTLY DECREASING from bottom to top.
    stack: List[int] = []
    for i in range(2 * n):
        v = nums[i % n]
        while stack and nums[stack[-1]] < v:
            ans[stack.pop()] = v
        # Critical gate: push only on first pass to avoid duplicate indices.
        if i < n:
            stack.append(i)
    return ans


def next_greater_elements_concat(nums: List[int]) -> List[int]:
    n = len(nums)
    if n == 0:
        return []
    doubled = nums + nums
    res = [-1] * (2 * n)
    stack: List[int] = []
    for i, v in enumerate(doubled):
        while stack and doubled[stack[-1]] < v:
            res[stack.pop()] = v
        stack.append(i)
    return res[:n]


def next_greater_elements_brute(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [-1] * n
    for i in range(n):
        for k in range(1, n):
            j = (i + k) % n
            if nums[j] > nums[i]:
                ans[i] = nums[j]
                break
    return ans


def edge_cases() -> None:
    # LC canonical
    assert next_greater_elements_doubled([1, 2, 1]) == [2, -1, 2]
    assert next_greater_elements_concat([1, 2, 1]) == [2, -1, 2]
    assert next_greater_elements_doubled([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]

    # Descending — only the max itself has -1; others find max via wraparound
    assert next_greater_elements_doubled([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]

    # All equal — strict means -1
    assert next_greater_elements_doubled([1, 1, 1]) == [-1, -1, -1]

    # Single
    assert next_greater_elements_doubled([42]) == [-1]

    # Empty (defensive)
    assert next_greater_elements_doubled([]) == []

    # Wrap-heavy
    assert next_greater_elements_doubled([3, 8, 4, 1, 2]) == [8, -1, 8, 2, 3]

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(1000):
        n = rng.randint(0, 30)
        nums = [rng.randint(0, 5) for _ in range(n)]   # small range → many duplicates
        a = next_greater_elements_doubled(nums)
        b = next_greater_elements_concat(nums)
        c = next_greater_elements_brute(nums)
        assert a == b == c, f"trial {trial}: nums={nums} a={a} b={b} c={c}"
    print("stress_test: 1000 random trials — doubled, concat, brute all agree.")


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