Нюхли в министерстве

Заметим, что ни один нюхль не пойдет по лестнице вниз: действительно, в этом случае нюхль заметит, что его этаж пропустили, и всё забудет.

Второе наблюдение. Не может быть такого, что нюхль вышел из лифта, а лифт поехал дальше вверх. В таком случае было нюхлю было бы выгоднее проехать на лифте еще хотя бы один этаж.

Пусть $$$maxf$$$ — максимальный этаж, на который могут поднять лифт нюхли. Тогда все, кому нужно попасть на этаж не выше $$$maxf$$$, попадут на него с помощью лифта, а все остальные выйдут на этаже $$$maxf$$$ и дальше пойдут пешком. Таким образом ответ — $$$\sum\limits_{i=1}^{n} \max(0, f_i - maxf)$$$.

Как вычислить $$$maxf$$$? Можно использовать один из следующих подходов: