Starting the ridge relay

The rules on this ridge leave the runner no choices. Every hut either leads to the road head or it does not.

The problem

Huts sit along a ridge west to east; altitudes lists their heights in metres in that order, and the last hut is the road head. A runner always moves east, one leg at a time, and the club's rules alternate:

• Every odd leg is a climb leg: go to the hut east of you with the lowest altitude among those at least as high as yours.
• Every even leg is a descent leg: go to the hut east of you with the highest altitude among those no higher than yours.

Equal altitude qualifies for both, ties go to the nearer hut, and a runner with nothing qualifying to the east abandons the relay there.

Count the huts a runner can leave and still reach the road head, including the road head itself.

Input. altitudes — a list of integers, hut altitudes west to east.

Output. The number of valid starting huts.

Example.

altitudes = [1860, 1810, 1840, 1820, 1850]   ->  3

From 1840 and from 1820 the climb leg lands on 1850, the road head. From 1810 the gentlest climb is 1820, not 1840, and the descent then wants a hut no higher than 1820 east of it — only 1850 is left. From 1860 nothing east is as high.

A second example, with a relay of two legs:

altitudes = [1820, 1850, 1810, 1860, 1830, 1840]   ->  3

From 1850: climb to 1860, descend to 1840, done. From 1820 the climb lands on 1830 and the descent has nowhere to go. From 1860, the highest hut, leg 1 fails.

Constraints.

• 1 <= len(altitudes) <= 2 * 10^4
• 1000 <= altitudes[i] <= 4000, repeats allowed

Hints

Approach

Brute force

Simulate from every hut. Each leg scans east for its target and a relay can run many legs, so the ridge costs O(n^3) — out of reach at 2 x 10^4 huts, and it re-runs the same relays from every hut feeding into them.

The insight

Both leg targets depend only on the hut you stand on, so precompute them once; reaching the road head is then a two-row table filled from the east westwards.

Every leg moves strictly east, so a hut's fate depends only on huts east of it: no cycles, and a right-to-left pass reads only finished entries. Two rows rather than one, because a hut behaves differently depending on which leg comes next.

The climb arrows come from a monotonic stack: walk the huts in ascending altitude, ties west-first, and let each arrival answer every stacked index west of it — that gives each hut the lowest qualifying altitude to its east, nearest of any tie. Descending altitude gives the descent arrows.

Algorithm

1. One hut means the answer is 1.
2. Sort indices by (altitude, index), sweep the stack, get after_climb.
3. Sort by (-altitude, index), sweep again, get after_descent.
4. Mark the road head reachable in both rows.
5. Going west: climb_ok[i] is descent_ok[after_climb[i]], descent_ok[i] is climb_ok[after_descent[i]], both false when the arrow is missing.
6. Return the count of true entries in climb_ok — leg 1 climbs.

Complexity

Time O(n log n) — the sorts dominate; the sweeps and the table pass are linear, each index pushed and popped once. Space O(n).

Solution

"""Which hut can start the relay — next-hut tables from a monotonic stack, then a backward DP."""


def next_hut(order, n):
    """For each hut, the hut one leg of a given kind sends it to, or None."""
    target = [None] * n
    stack = []
    # Huts arrive in leg order: the best target for a leg of this kind comes
    # first. Any hut already on the stack that lies west of the arrival is
    # answered by it, because nothing better can appear later.
    for i in order:
        while stack and i > stack[-1]:
            target[stack.pop()] = i
        stack.append(i)
    return target


def solve(altitudes):
    """How many huts a runner can start from and still reach the road head."""
    n = len(altitudes)
    if n == 1:
        return 1
    climb_order = sorted(range(n), key=lambda i: (altitudes[i], i))
    descent_order = sorted(range(n), key=lambda i: (-altitudes[i], i))
    after_climb = next_hut(climb_order, n)
    after_descent = next_hut(descent_order, n)

    # climb_ok[i]: the road head is reachable from hut i when the next leg is a
    # climb (an odd leg); descent_ok[i]: the same when the next leg descends.
    # Every leg moves strictly east, so filling right to left never reads an
    # entry that has not been written.
    climb_ok = [False] * n
    descent_ok = [False] * n
    climb_ok[n - 1] = descent_ok[n - 1] = True
    for i in range(n - 2, -1, -1):
        if after_climb[i] is not None:
            climb_ok[i] = descent_ok[after_climb[i]]
        if after_descent[i] is not None:
            descent_ok[i] = climb_ok[after_descent[i]]
    return sum(climb_ok)

TESTS = [
    (([1860, 1810, 1840, 1820, 1850],), 3),
    (([1820, 1850, 1810, 1860, 1830, 1840],), 3),
    (([1900, 1900, 1900],), 3),
    (([1500, 1400, 1300],), 1),
    (([1610, 1580, 1630],), 3),
    (([2100],), 1),
]

Pitfalls

• Breaking altitude ties toward the far hut. Sort ties by ascending index in both orders, or two huts at the same height, [1900, 1900], report 1 valid start instead of 2.
• Reading the rules as strictly higher and lower. Equal altitude qualifies for both legs; make them strict and [1900, 1900, 1900] gives 1, not 3.
• Filling the two rows west to east. climb_ok[i] reads a descent_ok entry that is still false, and the second example comes back as 2, not 3.

Variants

• Splitting the ripening shelf — the same fill-backwards discipline, over intervals rather than single huts.
• Loudest run on the board — one row, not two, because nothing there alternates.