В городе Нестриженске есть n лохматых жителей и всего один парикмахер. Житель номер i готов стричься в том и только в том случае, если ему придётся заплатить не больше v_i рублей (при этом, конечно, он предпочёл бы заплатить как можно меньше). Будем считать, что жители упорядочены по убыванию максимальной готовности платить: v_1 > v_2 > \dots > v_n..

Парикмахер стрижёт с рекордной скоростью и с нулевыми издержками. Ему, как и всем жителям, известен набор v_i, и он хотел бы с каждого жителя i собрать ровно v_i, тем самым получив максимально возможную прибыль. Однако он не в состоянии по внешнему виду жителя определить его номер и, соответственно, узнать его готовность платить. Конечно, можно поступить стандартным образом, назначив единую цену для всех клиентов. Однако парикмахер, в надежде получить больше, придумал следующую нестандартную схему продаж. Он объявляет n цен: v_1, v_2, \dots, v_n., и житель, придя в парикмахерскую, может подстричься по любой цене из этого списка на свой выбор, при условии что эта цена ещё не была выбрана другим жителем. Парикмахер делает это объявление по радио, после чего все жители бегут в парикмахерскую, чтобы успеть побыстрее.

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

а) Предположим, что чем больше номер жителя, тем раньше он прибегает в парикмахерскую. Сколько человек подстригутся? Какую прибыль получит парикмахер?

б) Пусть теперь наоборот: чем больше номер жителя, тем позже он прибежит в парикмахерскую. Сколько человек подстригутся? Может ли при этом получиться так, что парикмахер соберёт больше прибыли, чем если бы он назначил единую цену? (Естественно, единая цена была бы выбрана так, чтобы максимизировать прибыль.)

в) Решив пункты а) и б), парикмахер ещё хорошенько поразмышлял и придумал другую нестандартную схему продаж, на этот раз гарантированно (вне зависимости от того, в каком порядке прибегают жители) позволяющую ему с каждого жителя i собрать v_i. Опишите эту схему и докажите, что она приведёт именно к такому результату.