Різні сусідні#12962

Різні сусідні (Editorial)

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

Будемо будувати масив поступово:

Таким чином ми можемо побудувати масив , який задовольняє всі умови задачі.

Складність .