4008: 禁卫军

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：2

题目描述

数字王国正在挑选最强壮，最独一无二的勇士作为国王的禁卫军。

有 n 个数字士兵参与了这次选拔，分别为 w_1,w_2,...,w_n 其中可能存在多个相同的数字士兵，选拔的条件是如果这个数不能被剩下的 n-1 个数整除，就可以称为禁卫军。

请问，其中会有多少个士兵能顺利加入禁卫军。

输入

第一行读入一个整数 n。

第二行读入 n 个整数表示所有数字士兵 w_i，用空格隔开。

输出

输出一个整数，表示有多少个士兵能顺利加入禁卫军。

样例输入 复制 

5
3 7 9 16 17

样例输出 复制 

4

提示

样例

输入
复制 

5
3 7 9 16 17

输出
复制 

4

输入
复制 

5
1 2 3 4 5

输出
复制 

1

输入
复制 

5
2 2 3 3 5

输出
复制 

1
说明

样例 1 解释

数列中 3,7,16,17 不能被数列中其它整数整除，9 会被 3 整除，所以有 4 个。

数据规模

1 \leq w_i \leq 10^6。

对于 50 \% 的数据： 1 \leq n \leq 10000。

对于 100 \% 的数据： 1 \leq n \leq 100000。

来源/分类

提交提交记录统计露一手!