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}")

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgbmFtZWR0dXBsZQpmcm9tIG51bWJlcnMgaW1wb3J0IE51bWJlcgpmcm9tIHN0YXRpc3RpY3MgaW1wb3J0IG1lZGlhbl9sb3cKZnJvbSB0eXBpbmcgaW1wb3J0IEl0ZXJhYmxlCiAKRWxlbWVudCA9IG5hbWVkdHVwbGUoIkVsZW1lbnQiLCBbImhlaWdodCIsICJpbmRleCJdKQogCmRlZiBtYXhfaHRfZGlmZihoZWlnaHRzOiBJdGVyYWJsZVtOdW1iZXJdKSAtPiBJdGVyYWJsZVt0dXBsZVtFbGVtZW50LCBFbGVtZW50XV06CiAgICBlbHRzID0gW0VsZW1lbnQoaCwgaSkgZm9yIGksIGggaW4gZW51bWVyYXRlKGhlaWdodHMpXQogICAgaWYgbGVuKGVsdHMpICUgMiAhPSAwOgogICAgICAgIHJhaXNlIE5vdEltcGxlbWVudGVkRXJyb3IKICAgIG1pZGRsZSA9IG1lZGlhbl9sb3coZWx0cykKIAogICAgc3RhY2sgPSBbXQogICAgd2hpbGUgZWx0czoKICAgICAgICBpZiBub3Qgc3RhY2s6CiAgICAgICAgICAgIHN0YWNrLmFwcGVuZChlbHRzLnBvcCgpKQogICAgICAgIGlmIChzdGFja1stMV0gPD0gbWlkZGxlKSAhPSAoZWx0c1stMV0gPD0gbWlkZGxlKToKICAgICAgICAgICAgeWllbGQgc3RhY2sucG9wKCksIGVsdHMucG9wKCkKICAgICAgICBlbHNlOgogICAgICAgICAgICBzdGFjay5hcHBlbmQoZWx0cy5wb3AoKSkKIAogCmh0cyA9IFszLCAxLCA0LCA1LCA5LCAyLCA3LCA1XQpmb3IgYSwgYiBpbiBtYXhfaHRfZGlmZihodHMpOgogICAgcHJpbnQoZiJwYWlyIHthfSB3aXRoIHtifSIp