OI题库

题目描述

Nimo是小镇上最出色的木偶剧演员。他经常带着自己的木偶们在附近的镇上演出。为了方便起见，我们给每个木偶设定一个特征值pi，每个木偶都有一个原装的提线，提线的特征值和木偶是相等的，即也为pi。当一个木偶和一个提线的特征值相差超过1 时，提线将不能组装到木偶上。
现在木偶和提线被Nimo不小心全部打乱了，Nimo决定对这些木偶和提线重新配对。
他采取这样的策略：每次拿出一个木偶，再在未配对的提线里面随机抽一个可以组装到这个木偶上的提线，将它们配对，如果当前木偶没有可以配对的提线，Nimo将扔掉这个木偶。
现在他想知道的是，在最坏情况下，他最多会扔掉多少个木偶。

输入格式

测试文件中包含若干个测试点。
每个测试点包含两行。第一行包含一个整数N ，表示有N 个木偶。
接下来一行N 个整数，第i 个整数pi，表示第i 个木偶及其原装提线的特征值。

输出格式

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

样例输入

3
1 2 3
8
1 2 3 3 4 2 5 4

样例输出

1
2

样例说明

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

数据范围与约定

对于10% 的数据，满足 1 <= N <= 10。
对于20% 的数据，满足 1 <= N <= 20。
对于100%  的数据，满足 1 <= N <= 50，  1 <= pi <= 100。