Автор задачи: Даниил Орешников, разработчик: Константин Бац
Подойдем к задаче с конца: у нас есть два стека, и мы хотим первой изъять единицу. Для этого мы должны перемещать элементы между стеками, пока $$$1$$$ не окажется наверху одного из них. Понятно, что для этого необходимо вынуть из первого стека $$$a$$$ все элементы выше $$$1$$$ и переместить их во второй стек, после чего изъять единицу.
Заметим, что при этом если положить стеки $$$a$$$ и $$$b$$$ вершинами друг к другу, то относительный порядок элементов в них будет оставаться неизменным, пока мы просто перемещаем элементы между ними. Поэтому для повторения описанной выше операции для всех элементов от $$$2$$$ до $$$n$$$ достаточно поддерживать несколько величин:
Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, таким образом, надо просто определить его положение (первый или второй стек) и позицию в нем, после чего вынуть все элементы этого стека выше $$$i$$$, обновить ответ и обновить $$$m$$$. При обновлении $$$m$$$ надо аккуратно учитывать, в каком из стеков находилось $$$i$$$. А чтобы находить позицию какого-то числа в его стеке, достаточно найти его позицию во всей последовательности, после чего найти его разность с $$$m$$$.
Находить позицию числа в последовательности — то же самое, что и находить число элементов, которые все еще лежат в последовательности левее него, что можно делать с помощью дерева отрезков или дерева Фенвика с обновлением в точке и суммой на префиксе (поставим $$$0$$$ или $$$1$$$ в зависимости от того, был элемент удален или еще нет, и будем искать сумму таких флагов до исходной позиции интересующего нас числа). Суммарное время работы решения — $$$\mathcal{O}(n \log n)$$$.