Якщо в масиві усі сусідні елементи різні, то це масив вже задовольняє умови задачі. У інакшому випадку, якщо в масиві є сусідні елементи, які рівні, то значення max_{1\le i \le n}(b_i - a_i) буде хоча б 1.
Будемо будувати масив поступово:
b_1 = a_1,
для наступних елементів, якщо a_i \ne b_{i-1}, то ми можемо вибрати b_i = a_i,
інакше оберемо b_i = a_i + 1, щоб зробити сусідні елементи різними.
Таким чином ми можемо побудувати масив , який задовольняє всі умови задачі.
Складність .