from collections import namedtuple
from numbers import Number
from statistics import median_low
from typing import Iterable
 
Element = namedtuple("Element", ["height", "index"])
 
def max_ht_diff(heights: Iterable[Number]) -> Iterable[tuple[Element, Element]]:
    elts = [Element(h, i) for i, h in enumerate(heights)]
    if len(elts) % 2 != 0:
        raise NotImplementedError
    middle = median_low(elts)
 
    stack = []
    while elts:
        if not stack:
            stack.append(elts.pop())
        if (stack[-1] <= middle) != (elts[-1] <= middle):
            yield stack.pop(), elts.pop()
        else:
            stack.append(elts.pop())
 
 
hts = [3, 1, 4, 5, 9, 2, 7, 5]
for a, b in max_ht_diff(hts):
    print(f"pair {a} with {b}")