Проітеруємося по днях, і якщо відповідний день має додатну середню температуру повітря, то виведемо його номер.
Для того, щоб отримати мінімально можливе число, потрібно на кожну позицію поставити мінімально можливу цифру, тобто 0. Проте якщо це перша цифра числа, тоді потрібно поставити 1, бо число не може починатися з 0. Для максимального числа потрібно поставити всюди максимальну цифру, тобто 9.
Нам ніколи не вигідно міняти одне число більше ніж один раз, тому що ми можемо за одну операцію поміняти його на його кінцеве значення. Отже, мінімальна кількість змін рівна \(n\) мінус максимальна кількість елементів, що залишаться незмінними. Нескладно переконатися, що Зеник не може одночасно залишити незмінними числа \(a\) й \(b\), якщо вони різні, тобто він може залишити незмінними тільки однакові елементи. А отже нам потрібно знайти максимальну кількість однакових елементів і тоді від \(n\) відняти цю кількість.
Перестановка довжини \(i\) повинна містити лише числа від 1 до \(i\). Для кожного \(i\) від 1 до \(n\) розглянемо перші \(i\) чисел і подивимося, чи ці числа утворюють послідовний відрізок.
Нехай \(l_i\) — найлівіша позиція серед перших \(i\) чисел, а \(r_i\) — найправіша. Це означає, що елементи від 1 до \(i\) є на проміжку \([l_i, r_i]\). Цей проміжок буде перестановкою тоді й лише тоді, коли він містить лише елементи від 1 до \(i\).
Ми знаємо, що ці елементи там містяться, але необхідно ще забезпечити умову того, що там немає інших елементів. Ця умова рівносильна тому, що на цьому відрізку є рівно \(i\) елементів. Більш формально, якщо \(r_i - l_i + 1 = i\), тоді цей відрізок не містить зайвих елементів і є перестановкою.
Тобто нам достатньо пройтися по всіх \(i\) й для відповідного \(i\) знайти \(l_i\) та \(r_i\). Це нескладно зробити, знаючи \(l_{i - 1}\) і \(r_{i - 1}\). Тепер для кожного \(i\) виконаєм перевірку чи \([l_i, r_i]\) є перестановкою.