B. Johny English and Group Formation
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

After all these years as a spy Johny English found the hardest task of his life. He has to divide some people into groups. There are $$$n$$$ people standing in a line. The person at $$$i^{th}$$$ belongs to the country $$$c_i$$$. Johny English need to divide these people into groups following these conditions:

  1. Each person must be in some group
  2. Each group can consist of one or two people
  3. No two people from the same country can be in the same group
Johny English wants the total number of groups minimum. Now as his close friend you have to calculate the minimum number of groups he can divide those n people into.
Input

The first line of the Input contains two integers $$$n$$$ $$$(1\le n \le 10^5)$$$ denoting the number of people. The next line contains $$$n$$$ integers denoting $$$c_i$$$ $$$(1 \le c_i \le 10^5)$$$.

Output

Print the minimum number of groups Johny English can divide those $$$n$$$ people into.

Examples
Input
6
1 2 3 1 1 5
Output
3
Input
6
1 2 2 1 2 2
Output
4