human
I found an interesting problem on https://codeforces.com/problemset/problem/675/D:
(Легенда будет поправлена позже) У нас есть n целых чисел. Первое число становится корнем дерева, для остальных нужно реализовать добавление в дерево поиска и вывести для каждого n - 1 числа его непосредственного предка в дереве.

-----Входные данные-----

В первой строке записано одно целое число n (2 ≤ n ≤ 10^5) — количество чиcел. Во второй строке через пробел записаны n различных целых чисел a_{i} (1 ≤ a_{i} ≤ 10^9).

-----Выходные данные-----

Для всех i > 1 выведите непосредственного предка a_{i}

-----Примеры-----
Входные данные
3
1 2 3

Выходные данные
1 2

Входные данные
5
4 2 3 1 6

Выходные данные
4 2 2 4

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is the Python code you requested.

class RedBlackTree():
    _nil = (None, False, None, None, None)

    def __init__(self):
        self._root = RedBlackTree._nil

    def insert_key(self, key):
        y = self.search(key, True)
        z = [key, False, None, None, y]
        if y is RedBlackTree._nil:
            self._root = z
        else:
            y[2 if z[0] < y[0] else 3] = z
        z[2] = z[3] = RedBlackTree._nil
        z[1] = True
        self._insert_fixup(z)

    def _insert_fixup(self, z):
        while z[4][1]:
            if z[4] == z[4][4][2]:
                y = z[4][4][3]
                if y[1]:
                    z[4][1] = y[1] = False
                    z[4][4][1] = True
                    z = z[4][4]
                else:
                    if z == z[4][3]:
                        z = z[4]
                        self._left_rotate(z)
                    z[4][1] = False
                    z[4][4][1] = True
                    self._right_rotate(z[4][4])
            else:
                y = z[4][4][2]
                if y[1]:
                    z[4][1] = y[1] = False
                    z[4][4][1] = True
                    z = z[4][4]
                else:
                    if z == z[4][2]:
                        z = z[4]
                        self._right_rotate(z)
                    z[4][1] = False
                    z[4][4][1] = True
                    self._left_rotate(z[4][4])
        self._root[1] = False

    def _left_rotate(self, x):
        y = x[3]
        x[3] = y[2]
        if y[2] is not RedBlackTree._nil:
            y[2][4] = x
        y[4] = x[4]
        if x[4] is RedBlackTree._nil:
            self._root = y
        else:
            x[4][3 - (x == x[4][2])] = y
        y[2] = x
        x[4] = y

    def _right_rotate(self, y):
        x = y[2]
        y[2] = x[3]
        if x[3] is not RedBlackTree._nil:
            x[3][4] = y
        x[4] = y[4]
        if y[4] is RedBlackTree._nil:
            self._root = x
        else:
            y[4][2 + (y == y[4][3])] = x
        x[3] = y
  ...