Встаёшь в вершину, в которой лежит карта i и поднимаешься от неё до корня, и насчитываешь, сколько вершин лежит левее её (с учётом отложенных переворотов).

Или можно не возиться с отложенными переворотами, а протолкнуть их по всем вершинам на пути от корня до нашей вершины. Тогда надо будет просто считать, сколько вершин в дереве левее данной.