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

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgbmFtZWR0dXBsZQpmcm9tIG51bWJlcnMgaW1wb3J0IE51bWJlcgpmcm9tIHN0YXRpc3RpY3MgaW1wb3J0IG1lZGlhbl9sb3cKZnJvbSB0eXBpbmcgaW1wb3J0IEl0ZXJhYmxlCgpFbGVtZW50ID0gbmFtZWR0dXBsZSgiRWxlbWVudCIsIFsiaGVpZ2h0IiwgImluZGV4Il0pCgpkZWYgbWF4X2h0X2RpZmYoaGVpZ2h0czogSXRlcmFibGVbTnVtYmVyXSkgLT4gSXRlcmFibGVbdHVwbGVbRWxlbWVudCwgRWxlbWVudF1dOgogICAgZWx0cyA9IFtFbGVtZW50KGgsIGkpIGZvciBpLCBoIGluIGVudW1lcmF0ZShoZWlnaHRzKV0KICAgIGlmIGxlbihlbHRzKSAlIDIgIT0gMDoKICAgICAgICByYWlzZSBOb3RJbXBsZW1lbnRlZEVycm9yCiAgICBtaWRkbGUgPSBtZWRpYW5fbG93KGVsdHMpCgogICAgc3RhY2sgPSBbXQogICAgd2hpbGUgZWx0czoKICAgICAgICBpZiBub3Qgc3RhY2s6CiAgICAgICAgICAgIHN0YWNrLmFwcGVuZChlbHRzLnBvcCgpKQogICAgICAgIGlmIChzdGFja1stMV0gPD0gbWlkZGxlKSAhPSAoZWx0c1stMV0gPD0gbWlkZGxlKToKICAgICAgICAgICAgeWllbGQgc3RhY2sucG9wKCksIGVsdHMucG9wKCkKICAgICAgICBlbHNlOgogICAgICAgICAgICBzdGFjay5hcHBlbmQoZWx0cy5wb3AoKSkKCgpodHMgPSBbMywgMSwgNCwgNSwgOSwgMiwgNywgNV0KZm9yIGEsIGIgaW4gbWF4X2h0X2RpZmYoaHRzKToKICAgIHByaW50KGYicGFpciB7YX0gd2l0aCB7Yn0iKQ==