Min Operation

In each operation, either ship any single item, or ship any two items from different locations together. The two items need not be adjacent; the remaining items keep their relative order, but that does not restrict the next free choice. Find the minimum number of operations to ship all items.

输入格式

The first line contains n and the second line contains locations. The original length is written as n in the body and as m in the constraints and starter; it is unified as n: 1≤n≤100000, 1≤locations[i]≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
1 1 1 2

输出：

3

样例 2

输入：

3
1 2 3

输出：

2

样例 3

输入：

2
5 5

输出：

2

样例说明

The answers are 3, 2 and 2 respectively. In the first example only one 2 can be paired with a 1, and the other two 1s must ship alone.