"""Next Greater Element variants.

For each index i, compute the index/value of the next element strictly
greater than a[i] in the specified direction/order. Returns -1 (or None
index) when none exists. All variants O(n) via monotonic decreasing
stack of indices.
"""

from typing import List, Optional


def next_greater_right(nums: List[int]) -> List[int]:
    """For each i, index of first j>i with nums[j] > nums[i], else -1."""
    n = len(nums)
    res = [-1] * n
    stack: List[int] = []  # indices, values strictly decreasing
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            res[stack.pop()] = i
        stack.append(i)
    return res


def next_greater_left(nums: List[int]) -> List[int]:
    """For each i, index of last j<i with nums[j] > nums[i], else -1."""
    n = len(nums)
    res = [-1] * n
    stack: List[int] = []
    for i in range(n):
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        res[i] = stack[-1] if stack else -1
        stack.append(i)
    return res


def next_greater_circular(nums: List[int]) -> List[int]:
    """Circular: search wraps around; -1 if none greater in entire array."""
    n = len(nums)
    if n == 0:
        return []
    res = [-1] * n
    stack: List[int] = []
    # traverse 2n-1; only push first pass indices
    for k in range(2 * n - 1):
        i = k % n
        while stack and nums[stack[-1]] < nums[i]:
            res[stack.pop()] = i
        if k < n:
            stack.append(i)
    return res


def values_from_indices(nums: List[int], idxs: List[int]) -> List[Optional[int]]:
    return [nums[i] if i != -1 else None for i in idxs]


# brute-force oracles
def _brute_right(nums):
    n = len(nums)
    out = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                out[i] = j
                break
    return out


def _brute_left(nums):
    n = len(nums)
    out = [-1] * n
    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] > nums[i]:
                out[i] = j
                break
    return out


def _brute_circ(nums):
    n = len(nums)
    out = [-1] * n
    for i in range(n):
        for step in range(1, n):
            j = (i + step) % n
            if nums[j] > nums[i]:
                out[i] = j
                break
    return out