Перестановка по длинам монотонных подпоследовательностей

Для перестановки X чисел 1, 2, …, n определены два списка длины n:

• a[i] — длина самой длинной возрастающей подпоследовательности, которая заканчивается элементом X[i] (он в ней наибольший);
• b[i] — длина самой длинной убывающей подпоследовательности, которая начинается элементом X[i] (он в ней тоже наибольший).

Даны a и b; гарантируется, что хотя бы одна подходящая перестановка существует. Верните лексикографически наименьшую из них: X[0] как можно меньше, при равенстве — X[1] как можно меньше, и так далее. Ограничение: 1 ≤ n ≤ 2000, перебор перестановок не подходит.

Пример: [1, 2, 1, 3, 3, 1, 4, 1], [4, 4, 3, 4, 3, 2, 2, 1] → [4, 5, 3, 7, 6, 2, 8, 1].

Источник: Coding Competitions Archive, codejam/2013/round_2/erdsszekeres · © Google LLC · Apache-2.0 · условие переведено и дополнено