You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

  Farmer John 的聪明奶牛们离家出走了，分散排列在道路上，其中第 $i$ 头奶牛的数学成绩是 $m_i$。Farmer John 虽然想要把奶牛们全部抓回去，但由于他是一个喜欢对称的人，因此决定先抓捕数学成绩相同的奶牛。

  每次抓捕，Farmer John 选择两头数学成绩相同的奶牛，并把它们和它们之间的奶牛全抓走。Farmer John 想知道，在 不打乱奶牛顺序 的情况下，他最多能够抓到多少头奶牛。

Format

Input

  第一行一个整数 $n \space (n \leq 5\times 10^5)$，奶牛的数量

  第二行 $n$ 个整数，奶牛们的数学成绩 $m_i \space (1 \leq m_i \leq n)$

Output

  一个整数，Farmer John 能抓到的最大奶牛数

Samples

5
1 2 2 3 3

4

4
1 2 1 2

3

7
3 2 3 2 5 2 6

6