На днях Алексей закончил проведение соревнования по программированию для студентов из Берляндии. n студентов приняли участие в соревновании, i-й решил a_i задач. Теперь необходимо наградить некоторых участников. Алексей может вручать студентам дипломы трех степеней. Каждый студент или получит один диплом какой-либо степени, или не получит диплома совсем. Пусть cnt_x — количество студентов, награжденные дипломом степени x (1 ≤ x ≤ 3). Должны соблюдаться следующие условия:

• Для каждого x (1 ≤ x ≤ 3) cnt_x > 0;
• Для любых двух степеней x и y cnt_x ≤ 2·cnt_y.

Конечно, есть множество способов распределить дипломы. Пусть b_i — степень диплома, который получит i-й студент (или  - 1, если i-й студент останется без диплома). Также для любого x такого, что 1 ≤ x ≤ 3, пусть c_x — максимальное количество задач, решенных студентом, получившим диплом степени x, а d_x — минимальное количество задач, решенных студентом, получившим диплом степени x. Алексей хочет раздать дипломы таким образом, чтобы:

1. Если студент i решил больше задач, чем студент j, то он должен быть награжден не хуже студента j (невозможно, чтобы студент j получил диплом, а i — нет, и невозможно, чтобы оба получили диплом и b_j < b_i);
2. d₁ - c₂ должно быть максимально;
3. Среди всех способов максимизировать предыдущее выражение d₂ - c₃ должно быть максимально;
4. Среди всех способов удовлетворить предыдущие условия d₃ - c_- 1 должно быть максимально, где c_- 1 — максимальное количество задач, решенных студентом, не получившим диплома (или 0, если все студенты получили диплом).

Помогите Алексею найти способ наградить участников!