2708 - [Violet 1]木偶

Nimo是小镇上最出色的木偶剧演员。他经常带着自己的木偶们在附近的镇上演出。

为了方便起见，我们给每个木偶设定一个特征值 $p_i$ ，每个木偶都有一个原装的提线，提线的特征值和木偶是相等的,即也为 $p_i$

当一个木偶和一个提线的特征值相差超过 $1$ 时,提线将不能组装到木偶上。

现在木偶和提线被Nimo不小心全部打乱了,Nimo决定对这些木偶和提线重新配对。

他采取这样的策略:每次拿出一个木偶，再在未配对的提线里面随机抽一个可以组装到这个木偶上的提线,将它们配对,如果当前木偶没有可以配对的提线,Nimo将扔掉这个木偶。

现在他想知道的是,在最坏情况下,他最多会扔掉多少个木偶。

Input

测试文件中包含若干个测试点。

每个测试点包含两行。第一行包含一个整数 $N$ ,表示有 $N$ 个木偶。

接下来一行 $N$ 个整数,第 $i$ 个整数 $p_i$ ,表示第 $i$ 个木偶及其原装提线的特征值。

Output

一行一个整数，表示最多可能扔掉多少个木偶。

Examples

Input

1
2
1
54
2
8 9
3
1 2 3
2
56 60
3
59 59 57
3
51 55 59
5
1 2 3 2 4
4
87 70 81 34
4
50 55 58 59
6
1 2 3 4 5 6
6
1 2 3 3 4 5
8
1 2 3 3 4 2 5 4
9
22 23 52 61 39 38 1 40 17

Output

Hint

样例解释

对于样例1，Nimo可能会把第2个木偶和第1个木偶的原配提线配对,第3个木偶利第2个木偶的原配提线配对,这样第3个木偶就会被扔掉。

对于 $10\%$ 的数据,满足 $1\le N\le10$ .

对于 $20\%$ 的数据,满足 $1\le N\le20$ 。

对于 $100\%$ 的数据,满足 $1\leqN\leq50，1\leqp_i\leq100$ 。

Time Limit	1 second
Memory Limit	128 MB

Stats

上一题下一题