Старожилы ЛКШ могут помнить смены, в которых каждый школьник получал на вечёрку желаемый напиток. Или не совсем?
В домике живёт \(n\) школьников, каждый из них в анкете отметил свой любимый напиток \(a_i\). Таким образом, известны \(n\) целых чисел \(a_1, a_2, \dots, a_n\), где \(a_i\) (\(1 \le a_i \le k\)) — номер любимого напитка \(i\)-го школьника. Все напитки пронумерованы от \(1\) до \(k\).
В наличии есть неограниченное количество наборов напитков. Каждый набор содержит ровно две порции одинакового напитка. Иными словами, в наличии есть \(k\) типов наборов, \(j\)-й набор содержит две порции напитка \(j\). Количество наборов каждого из \(k\) типов — неограниченно.
Известно, что на домик будет выдано наименьшее количество наборов, но при этом достаточное, чтобы хватило всем школьникам. Конечно, количество наборов будет равно \(\lceil \frac{n}{2} \rceil\), где \(\lceil x \rceil\) обозначает округление вверх числа \(x\).
После получения наборов школьники самостоятельно разберут порции. Заметим, что если \(n\) является нечётным числом, то одна порция останется лишней и её выпьет преподаватель.
Какое наибольшее количество школьников смогут получить любимый напиток при оптимальном выборе \(\lceil \frac{n}{2} \rceil\) наборов и распределении порций между школьниками?
Примечание
В первом примере школьники могут выбрать три набора с напитками \(1\), \(1\) и \(2\) (то есть у них будет два набора с двумя \(1\)-ми напитками и набор с двумя \(2\)-ми напитками, то есть порции будут иметь вид: \(1, 1, 1, 1, 2, 2\)). Тогда все школьники кроме второго получат любимый напиток.
Другим возможным способом являются наборы с напитками \(1\), \(2\) и \(3\). В таком случае порции будут иметь вид: \(1, 1, 2, 2, 3, 3\). Тогда все школьники, кроме одного получат желаемые напитки. Единственный школьник, который не получит любимый напиток, будет один из тех для кого \(a_i = 1\) (то есть первый, третий или четвертый).