Зауважимо, що b_i \ge b_{i-1} та c_i \ge c_{i+1}, оскільки при додаванні нових значень в множину їх mex не може зменшуватись.
Якщо b_i \ne b_{i-1}, то повинно виконуватись a_i=b_{i-1}, адже жодне число зліва від не дорівнює b_{i-1}, а разом з a_i уже хоча б одне число має бути рівним b_{i-1}. Аналогічно, a_i=c_{i+1}, якщо c_i \ne c_{i+1}.
Таким чином, ми маємо вже деякі значення зафіксовані. Подивимось, що ще необхідно, щоб виконувалась умова. Якщо b_i \ne b_{i-1} також потрібно, щоб усі значення b_{i-1}+1, b_{i-1}+2, \dots, b_{i}-1 були на префіксі [1, i-1] хоча б раз. Додамо обмеження для таких значень v \in [b_{i-1}+1, b_i-1], що вони повинні бути хоча б раз на проміжку [1, l_v], тут l_v=i-1. Аналогічно зробимо обмеження, що значення повинне бути хоча б раз на суфіксі [r_v, n].
Викинемо ті обмеження, які вже виконані уже зафіксованими значеннями. Далі зауважимо, якщо для значень u < v існують обмеження на префікс, то l_u \le l_v. Та якщо на суфікс, то r_u \ge r_v. Цю властивість можна отримати напряму з того, як ми генеруємо обмеження та того, що масиви та неспадний і незростаючий відповідно.
Тобто, якщо u<v, то і префікс і суфікс на який потрібно поставити є більшим за відповідний префікс чи суфікс для . Це означає, що ми можемо жадібно ставити значення від найменших.
Будемо розглядати значення від 1 до . Якщо для цього значення немає обмежень, то можна його пропустити. Якщо для значення існують обмеження [1, l_v], [r_v, n], r_l \le l_v та на проміжку [r_v, l_v] ще є незаповнені значення, то поставимо туди значення . Інакше, якщо існує обмеження [1, l_v], то поставимо значення на найлівіше вільне місце, та на найправіше вільне місце, якщо існує обмеження [r_v, n].
Для зберігання вільних позицій використаємо структуру даних set. Якщо в кінці залишились ще вільні позиції, то поставимо там будь-які великі значення.
Складність розв’язку O(n \log n).