D. Add 9 Zeros Ⅱ
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ of $$$n$$$ distinct integers.

Now you need to select $$$m$$$ integers from the array $$$a$$$ to form a new array $$$b$$$ so that $$$b$$$ satisfies the following condition:

  • There has no two integers $$$i, j$$$ $$$(1 \le i, j \le m)$$$ satisfies $$$b_i = b_j + 9$$$.

You need to answer the maximum value of $$$m$$$.

Input

The first line of the input contains one integer $$$n$$$ $$$(1\le n\le 2 \times 10^5)$$$.

The second line contains $$$n$$$ distinct integers $$$a_1,a_2,...,a_n(1\le a_i \le 10^9)$$$.

Output

Print one integer — the number satisfying the conditions above.

Example
Input
9
11 4 5 14 1 9 19 8 10
Output
7