Calculate Min Shipments (Warehouse Pairing)

One shipment sends two items from different warehouses, or a single item on its own; find the minimum number of shipments needed to send everything. This problem has the same rules as Amazon45 and keeps its own independent source number.

输入格式

The first line contains n (1..100000), and the second line contains n warehouse numbers (1..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

5
2 9 7 8 8

输出：

3

样例 2

输入：

2
1 1

输出：

2

样例 3

输入：

3
1 2 3

输出：

2

样例说明

Example 1: the two 8s are paired with 2 and 9 respectively, and 7 is shipped alone, 3 in total. Example 2: items from the same warehouse cannot be paired, 2 shipments. Example 3: pair any two items and ship the remaining one alone, 2 shipments.