Олимпиада имени Леонарда Эйлера 2025-2026 учебный год, I тур регионального этапа

В электронную таблицу, где две строки и $n$ столбцов, в произвольном порядке записаны все натуральные числа от 1 до $2n$ (в каждой клетке — одно число). В полдень каждого дня компьютер случайным образом выбирает столбец, где число из верхней строки больше числа из нижней, и меняет эти два числа местами, а затем случайным образом переставляет числа в верхней строке. В момент, когда в каждом столбце верхнее число оказывается меньше нижнего, процесс заканчивается. Докажите, что такой процесс не может происходить дольше, чем $n^2$ дней. ( М. Магин, Р. Баринов )