Чтобы удовлетворить свою любовь к собиранию носков в пары, Феникс принес свои \(n\) носков (\(n\) — четное) в магазин по продаже носков. Каждый его носок определенного цвета \(c_i\) и либо левый, либо правый.
Феникс может заплатить один доллар магазину, чтобы:
- либо перекрасить какой-то носок в любой цвет \(c'\) \((1 \le c' \le n)\),
- либо превратить левый носок в правый,
- либо превратить правый носок в левый.
Магазин может производить любое из изменений любое количество раз. Заметим, что цвет левого носка не меняется, когда он превращается в правый, и наоборот.
Два носка образуют пару, если это левый и правый носок одинакового цвета. Какую минимальное количество денег нужно заплатить Фениксу, чтобы собрать \(n/2\) пар? Каждый носок должен попасть ровно в одну пару.
Выходные данные
Для каждого набора входных данных, выведите одно число — минимальное количество денег, которое нужно заплатить Фениксу, чтобы собрать \(n/2\) пар носков. Каждый носок должен попасть ровно в одну пару.
Примечание
В первом наборе, Феникс может заплатить \(2\) доллара для того, чтобы:
- перекрасить носок \(1\) в цвет \(2\),
- перекрасить носок \(3\) в цвет \(2\).
В результате он получит
\(3\) пары. Например, пары
\((1, 4)\),
\((2, 5)\) и
\((3, 6)\).
Во втором наборе, Феникс может заплатить \(3\) доллара, чтобы:
- превратить носок \(6\) из правого в левый,
- перекрасить носок \(3\) в цвет \(1\),
- перекрасить носок \(4\) в цвет \(1\).
В результате он получит
\(3\) пары. Например, пары
\((1, 3)\),
\((2, 4)\) и
\((5, 6)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3
|
2
3
5
3
|